ข้อความโจทย์
กำหนดเมทริกซ์ไบนารีขนาด N แถว M คอลัมน์ การดำเนินการที่อนุญาตคือเลือกดัชนี (x, y) ใดๆ และสลับ (toggle) องค์ประกอบทั้งหมดในสี่เหลี่ยมผืนผ้าที่มุมซ้ายบนคือ (0, 0) และมุมขวาล่างคือ (x-1, y-1) การสลับหมายถึงการเปลี่ยน 1 เป็น 0 และ 0 เป็น 1 งานคือหาจำนวนการดำเนินการขั้นต่ำเพื่อให้องค์ประกอบทั้งหมดของเมทริกซ์เป็น 1
ตัวอย่าง
หากเมทริกซ์นำเข้าเป็น {0, 0, 0, 1, 1} {0, 0, 0, 1, 1} {0, 0, 0, 1, 1} {1, 1, 1, 1, 1} {1, 1, 1, 1, 1} คำตอบคือ 1ในหนึ่งการเคลื่อนที่ ให้เลือก (3, 3) เพื่อทำให้เมทริกซ์ทั้งหมดประกอบด้วย 1 เท่านั้น
อัลกอริทึม
แนวคิดคือเริ่มจากจุดสิ้นสุด (N-1, M-1) และวนลูปเมทริกซ์ในลำดับย้อนกลับ ทุกครั้งที่พบเซลล์ที่มีค่า 0 ให้สลับมัน
ตัวอย่าง
#include <iostream> #define ROWS 5 #define COLS 5 using namespace std; int getMinOperations(bool arr[ROWS][COLS]) { int ans = 0; for (int i = ROWS - 1; i >= 0; i--) { for (int j = COLS - 1; j >= 0; j--) { if (arr[i][j] == 0) { ans++; for (int k = 0; k <= i; k++) { for (int h = 0; h <= j; h++) { if (arr[k][h] == 1) arr[k][h] = 0; else arr[k][h] = 1; } } } } } return ans; } int main() { bool mat[ROWS][COLS] = { 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }; cout << "Minimum required operations = " << getMinOperations(mat) << endl; return 0; }ผลลัพธ์
เมื่อคอมไพล์และรันโปรแกรมข้างต้น จะได้ผลลัพธ์ดังนี้
Minimum required operations = 3
