C++에서 이진 행렬을 0행렬로 변환하는 연산 수를 계산하는 프로그램

<시간/>

이진 행렬이 있다고 가정합니다. 이제 하나의 셀을 가져 와서 모든 인접 셀(위, 아래, 왼쪽, 오른쪽)을 뒤집는 작업을 고려하십시오. 행렬에 0만 포함되도록 필요한 최소 연산 수를 찾아야 합니다. 솔루션이 없으면 -1을 반환합니다.

따라서 입력이 다음과 같으면

0	0
1	0

그러면 출력은 3이 됩니다.

C++에서 이진 행렬을 0행렬로 변환하는 연산 수를 계산하는 프로그램

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

배열 디렉토리 크기 정의:4 x 2 :={{1, 0}, {0, 1}, { - 1, 0}, {0, - 1}}
const int inf =10^6
getPos() 함수를 정의하면 i, j가 필요합니다.
i * c + j를 반환
하나의 함수 getCoord() 정의 x
- 한 쌍의 ret 정의
- ret[0] :=x / c
- ret[1] :=x 모드 c
- 반환
기본 방법에서 다음을 수행합니다.
마스크 :=0
r :=행렬의 행 수
c :=행렬의 열 개수
마지막 :=r * c
초기화 i의 경우:=0, i
j 초기화의 경우:=0, j
mask :=마스크 XOR (행렬[i, j] * 2^getPos(i, j))

크기 512의 배열 dist를 정의하고 -1로 채움

하나의 대기열 정의

q에 마스크 삽입

거리[마스크] :=0

동안(q는 비어 있지 않음) 다음을 수행합니다.

mask :=q의 첫 번째 요소
q에서 요소 삭제
i를 초기화하려면:=0, i <마지막일 때 업데이트(i를 1만큼 증가), 다음을 수행합니다.
- 한 쌍의 좌표 정의
- x :=좌표[0]
- y :=좌표[1]
- nmask :=마스크
- nmask :=nmask XOR 2^i
- 초기화 k의 경우:=0, k <4일 때 업데이트(k를 1만큼 증가), 수행:
  - nx :=x + dir[k, 0]
  - ny :=y + dir[k, 1]
  - nx와 ny가 행렬의 범위에 없으면:
    - 다음 부분은 무시하고 다음 반복으로 건너뜁니다.
  - pos :=getPos(nx, ny)
  - nmask :=nmask XOR(2^pos)
- dist[nmask]가 -1 또는 dist[nmask]> dist[mask] + 1과 같은 경우:
  - dist[nmask] :=dist[mask] + 1
  - nmask를 q에 삽입

반환 거리[0]

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

예시

#include
using namespace std;
int dir[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
int c;
int r;
int last;
const int inf = 1e6;

int getPos(int i, int j){
   return i * c + j;
}
pair getCoord(int x){
   pair ret;
   ret.first = x / c;
   ret.second = x % c;
   return ret;
}

int solve(vector>& matrix) {
   int mask = 0;
   r = matrix.size();
   c = r ? matrix[0].size() : 0;
   last = r * c;
   for(int i = 0; i < r; i++){
      for(int j = 0; j < c; j++){
         mask ^= (matrix[i][j] << getPos(i, j));
      }
   }
   vector dist(1 << 9, -1);
   queue q;
   q.push(mask);
   dist[mask] = 0;
   while(!q.empty()){
      mask = q.front();
      q.pop();
     
      for(int i = 0; i < last; i++){
         pair coord = getCoord(i);      
         int x = coord.first;
         int y = coord.second;
         
         int nmask = mask ;
         nmask ^= (1 << i);
         for(int k = 0; k < 4; k++){
            int nx = x + dir[k][0];
            int ny = y + dir[k][1];
            if(nx < 0 || nx >= r || ny < 0 || ny >= c)
               continue;
            int pos = getPos(nx, ny);
            nmask ^= (1 << pos);
         }
         
         if(dist[nmask] == -1 || dist[nmask] > dist[mask] + 1){
            dist[nmask] = dist[mask] + 1;
            q.push(nmask);
         }
      }
   }
   return dist[0];
}
int main(){
   vector> v = {{0, 0},{1, 0}};
   cout << solve(v);
}

입력

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