読者です 読者をやめる 読者になる 読者になる

AOJ0131 Doctor's Strange Particles

解法
蟻本の反転の考え方を使う。最上部を踏むか踏まないか2^10で決め打ちし、2段目からはマスの一つ上が 1 であるなら 0 に埋めることを 9*10回 繰り返す。反転のオーダーは O(M*N*2^N)

蛇足
Emacsのゲームにある 5x5 で遊んだらイメージがしっかり掴めて実装が割りかしスムーズに進んだ。最上部を順に 1, 2, 4, 8, 16 と割り当て、32通りの決め打ち作業からゲームを進める。実際は元のマップの対称性より、16通り試して遊んでみるだけで良い。

#include <bits/stdc++.h>
using namespace std;

const int dx[] = {-1,1,0,0};
const int dy[] = {0,0,-1,1};

int ori[10][10];
int arr[10][10];
int arr2[10][10];
    
void flip(int i, int j) {
  arr[i][j] = 1 - arr[i][j];
  arr2[i][j] = 1 - arr2[i][j];
  for(int k=0; k<4; k++) {
    int nx = j+dx[k], ny = i+dy[k];
    if(0<=ny && ny<10 && 0<=nx && nx<10) {
      arr[ny][nx] = 1 - arr[ny][nx];
    }
  }
}

int main() {
  int Tc; cin >> Tc;
  
  while(Tc--) {
    
    for(int i=0; i<10; i++)
      for(int j=0; j<10; j++)
        cin >> ori[i][j];
    
    bool good = 0;
    for(int I=0; I<(1<<10); I++) {
      memset(arr2, 0, sizeof(arr2));
      memcpy(arr, ori, sizeof(ori));
      bool ok = 1;
      for(int i=0; i<10; i++) {
        for(int j=0; j<10; j++) {
          
          if(i == 0) {
            if((I>>j) & 1) {
              if(arr[0][j] == 0) flip(0, j);
            }
            else {
              if(arr[0][j] == 1) flip(0, j);
            }
          }
          else {
            if(arr[i-1][j] == 1) flip(i, j);
          }
          
        } 
      }
      
      for(int i=0; i<10; i++) {
        if(arr[9][i]) ok = 0;
      }
      if(ok) {
        good = 1;
        break;
      }
    }
    if(good) {
      for(int i=0; i<10; i++) {
        for(int j=0; j<10; j++) {
          if(j) cout << " ";
          cout << arr2[i][j];
        }
        cout << endl;
      }
    }
  }
  
  return 0;
}