C++에서 이진 행렬을 0행렬로 변환하기 위한 최소 뒤집기 횟수

<시간/>

m x n 이진 행렬 매트가 있다고 가정합니다. 한 단계에서 우리는 하나의 셀을 선택하고 해당 비트와 4개의 이웃이 있는 경우 모두 뒤집을 수 있습니다. mat를 0행렬로 변환하는 데 필요한 최소 단계 수를 찾아야 합니다. 솔루션이 없으면 -1을 반환합니다.

따라서 주어진 입력이 [[0,0], [0,1]]과 같으면 변경은 -

와 같습니다.

따라서 3단계가 필요하며 출력은 3이 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

n :=행 수, m :=열 수, x :=0
초기화 i의 경우:=0, i
j 초기화의 경우:=0, j
j 초기화의 경우:=0, j
x :=x + 왼쪽 시프트 매트[i][j] 값 (i * m) + j) 횟수

2^(n * m) 셀로 배열 dp를 정의하고 -1로 채웁니다.

dp[x] :=0

하나의 대기열 정의

q에 x 삽입

동안(q는 비어 있지 않음) -

current :=q의 첫 번째 요소, q에서 요소 삭제

전류가 0과 같으면 -

dp[현재]를 반환

초기화 i의 경우:=0, i

j 초기화의 경우:=0, j

temp :=현재

temp :=임시 XOR 2^ (i * m) + j)

초기화 k의 경우:=0, k <4일 때 업데이트(k를 1만큼 증가), 수행 -

ni :=i + dir[k][0]
nj :=j + dir[k][1]
ni <0 또는 nj <0 또는 ni>=n 또는 nj>=m이면 −
- 다음 부분은 무시하고 다음 반복으로 건너뜁니다.
- temp :=임시 XOR 2^ (ni * m) + nj)

dp[temp]가 -1과 같으면 -

dp[temp] :=dp[현재] + 1
q에 온도 삽입

반환 -1

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

#include <bits/stdc++.h>
using namespace std;
int dir[4][2] = {{1, 0}, {-1, 0}, {0, -1}, {0, 1}};
class Solution {
public:
   int minFlips(vector<vector<int>>& mat) {
      int n = mat.size();
      int m = mat[0].size();
      int x = 0;
      for(int i = 0; i < n; i++){
         for(int j = 0; j < m; j++){
            x += (mat[i][j] << ((i * m) + j));
         }
      }
      vector < int > dp(1 << (n*m), -1);
      dp[x] = 0;
      queue <int> q;
      q.push(x);
      while(!q.empty()){
         int current = q.front();
         q.pop();
         if(current == 0)return dp[current];
         for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
               int temp = current;
               temp ^= (1 << ((i *m) + j));
               for(int k = 0; k < 4; k++){
                  int ni = i + dir[k][0];
                  int nj = j + dir[k][1];
                  if(ni < 0 || nj < 0 || ni >= n || nj >= m)continue;
                  temp ^= (1 << ((ni *m) + nj));
               }
               if(dp[temp] == -1){
                  dp[temp] = dp[current] + 1;
                  q.push(temp);
               }
            }
         }
      }
      return -1;
   }
};
main(){
   Solution ob;
   vector<vector<int>> v = {{0,0},{0,1}};
   cout << (ob.minFlips(v));
}

입력

{{0,0},{0,1}}