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

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