การดำเนินการขั้นต่ำที่จำเป็นในการตั้งค่าองค์ประกอบทั้งหมดของเมทริกซ์ไบนารีใน C++

คำชี้แจงปัญหา

รับเมทริกซ์ไบนารีของ N แถวและ M คอลัมน์ การดำเนินการที่อนุญาตบนเมทริกซ์คือการเลือกดัชนีใดๆ (x, y) และสลับองค์ประกอบทั้งหมดระหว่างสี่เหลี่ยมผืนผ้าที่มีด้านซ้ายบนเป็น (0, 0) และด้านล่างขวาเป็น (x-1, y-1) การสลับองค์ประกอบหมายถึงการเปลี่ยน 1 เป็น 0 และ 0 เป็น 1 ภารกิจคือการค้นหาการดำเนินการขั้นต่ำที่จำเป็นในการตั้งค่าองค์ประกอบทั้งหมดของเมทริกซ์เช่นทำให้องค์ประกอบทั้งหมดเป็น 1

ตัวอย่าง

If input matrix is {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}
Then answer is 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