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; }