在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)使整个矩阵仅包含1s。

算法

这个想法是从端点（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