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