การตัดขั้นต่ำสามารถทำได้ในกระดานหมากรุกโดยไม่แบ่งออกเป็น 2 ส่วนใน C++

แนวคิด

จาก A x B Chessboard ภารกิจคือการคำนวณจำนวนการตัดสูงสุดที่เราสามารถสร้างใน Chessboard เพื่อไม่ให้กระดานหมากรุกถูกแบ่งออกเป็น 2 ส่วน

ตัวอย่าง

ตัวอย่างได้รับด้านล่าง −

ป้อนข้อมูล

A = 2, B = 4

ผลลัพธ์

Number of maximum cuts = 3

ป้อนข้อมูล

A = 2, B = 2

ผลลัพธ์

Number of maximum cuts = 1

วิธีการ

• สำหรับ A =2, B =2 เราสร้างได้เพียง 1 ชิ้นเท่านั้น (ทำเครื่องหมายเป็นสีแดง) ถ้าเราสร้างอีก 1 ชิ้น กระดานหมากรุกจะแบ่งเป็น 2 ชิ้น

• สำหรับ A =2, B =4 เราสามารถตัดได้ 3 ครั้ง (เครื่องหมายเป็นสีแดง) ถ้าเราสร้างอีก 1 ชิ้น กระดานหมากรุกจะแบ่งเป็น 2 ชิ้น

ด้วยเหตุนี้จึงสังเกตได้ว่าไม่มี ของการตัด =(A-1) * (B-1)

ตัวอย่าง

//This is C++ implementation of above approach
#include <bits/stdc++.h>
using namespace std;
// function that calculates the maximum no. of cuts
int numberOfCuts1(int A, int B){
   int result1 = 0;
   result1 = (A - 1) * (B - 1);
   return result1;
}
// Driver Code
int main(){
   int A = 4, B = 4;
   // Calling function.
   int Cuts = numberOfCuts1(A, B);
   cout << "Maximum cuts = " << Cuts;
   return 0;
}

ผลลัพธ์

Maximum cuts = 9