ตัดกระดานหมากรุกไม่ให้แยกเป็น 2 ส่วน
กำหนดกระดานขนาด M x N ต้องการหาจำนวนการตัด (Cut) สูงสุดที่ทำได้ โดยที่กระดานยังคงต่อเนื่องเป็นชิ้นเดียว (ไม่แยกเป็น 2 ส่วน)
สูตร: (M - 1) * (N - 1)
เหตุผล: กระดานมี M*N ช่อง สามารถตัดขอบระหว่างช่องได้ทั้งหมด M*(N-1) + N*(M-1) ขอบ เพื่อไม่ให้แยกส่วน ต้องเหลือขอบอย่างน้อย M*N - 1 ขอบ (Spanning Tree) ดังนั้นตัดได้สูงสุด = ขอบทั้งหมด - (M*N - 1) = (M-1)*(N-1)
โค้ดตัวอย่าง Python
def max_cuts_count(M, N):
return (M - 1) * (N - 1)
M, N = 2, 4
print(max_cuts_count(M, N)) # 3
อินพุต / เอาต์พุต
Input: 2, 4
Output: 3
