[TIOJ] 1046. B.陷阱

題目連結:http://tioj.infor.org/problems/1046

---

一開始看到的時候不知所措，後來瀚瀚(?講了我才知道。其實只要枚舉最上面那排要怎麼按，下面的所有按鈕就可以知道要怎麼按了，因為一定要把上面的按掉這樣，複雜度$O(2^N)$。

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
#define X first
#define Y second

const int INF = 1000000;

char game[10][10];
int n, m;
int dfs1(int);
int dfs2();
inline bool check();
inline void click(int,int);

int main(){
	while(true){
		char c;
		for(n=0;;n++){
			c=getchar();
			for(m=0;c!='\n';m++){
				if(c=='#')break;
				game[n][m]=c;
				c=getchar();
			}
			if(c=='#')break;
			game[n][m]='\0';
			if(game[n][0]=='\0') break;
		}
		if(c=='#')break;
		m=strlen(game[0]);
		int ans = dfs1(0);
		if(ans >= INF) puts("Another Skeleton in the Ancient Tomb!");
		else printf("Minimum Steps : %d\n", ans);
	}
	return 0;
}

int dfs1(int pos){
	if(pos==m) return dfs2();
	int off = dfs1(pos+1);
	click(0, pos);
	int on = dfs1(pos+1)+1;
	click(0, pos);
	return min(off, on);
}

int dfs2(){
	queue<PII> qq;
	int r=0;
	for(int i=1;i<n;i++){
		for(int j=0;j<m;j++){
			if(game[i-1][j]=='O'){
				click(i, j);
				qq.push({i, j});
				r++;
			}
		}
	}
	if(!check()) r=INF;
	while(!qq.empty()){
		auto tp=qq.front();qq.pop();
		click(tp.X, tp.Y);
	}
	return r;
}

bool check(){
	for(int i=0;i<m;i++)
		if(game[n-1][i]=='O') return false;
	return true;
}

inline void click(int i, int j){
	#define inv(x) (((x)=='O')?'X':'O')
	game[i][j] = inv(game[i][j]);
	if(i-1 >= 0) game[i-1][j] = inv(game[i-1][j]);
	if(j-1 >= 0) game[i][j-1] = inv(game[i][j-1]);
	if(i+1 < n) game[i+1][j] = inv(game[i+1][j]);
	if(j+1 < m) game[i][j+1] = inv(game[i][j+1]);
	#undef inv
}