记录编号 287996 评测结果 AAAAAAAAAAAAAAAAAAAA
题目名称 [NOIP 2010冲刺七]翻转游戏 最终得分 100
用户昵称 Gravatar洛克索耶夫 是否通过 通过
代码语言 C++ 运行时间 0.083 s
提交时间 2016-08-02 16:12:37 内存使用 0.44 MiB
显示代码纯文本
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;

int ans = 0x3f3f3f3f, cnt;
bool appear[130000];//数组的0与1看成一个16位的二进制数 
struct Array{
	bool G[10][10];
	int cnt;
	
	void clear()
	{
		memset(G, 0, sizeof(G));
		cnt = 0;
	}
	
	void Change(int a, int b)//行 列 
	{
		G[a][b] = !G[a][b];
		G[a-1][b] = !G[a-1][b];
		G[a+1][b] = !G[a+1][b];
		G[a][b+1] = !G[a][b+1];
		G[a][b-1] = !G[a][b-1];
	}	
	
	bool Check()
	{
		int tmp1 = 16, tmp2 = 16;
		for(int i = 1; i <= 4; i++){
			for(int j = 1; j <= 4; j++){
				if(G[i][j])	tmp1--;
				else		tmp2--;
			}
		}
		if(tmp1 == 0 || tmp2 == 0){
			return 1;
		}	
		return 0;
	}	
	
	int Binary()
	{
		int k = 0, tmp = 0;
		for(int i = 1; i <= 4; i++){
			for(int j = 1; j <= 4; j++){
				k++;
				tmp += G[i][j] << k;	
			}
		}
		return tmp;
	}
};
queue <Array> Q;

int main()
{
	freopen("flip.in", "r", stdin); freopen("flip.out", "w", stdout);
	Array begin; begin.clear();
	char ch;
	for(int i = 1; i <= 4; i++){
		for(int j = 1; j <= 4; j++){
			cin >> ch;
			if(ch == 'b')	begin.G[i][j] = 0;
			else			begin.G[i][j] = 1;
		}
	}
	if(begin.Check()){
		puts("0");
		goto END;
	}
	
	Q.push(begin);
	appear[begin.Binary()] = 1;
	while(!Q.empty()){
		Array top = Q.front();
		Q.pop();
//		printf("%d\n", top.Binary());
//		for(int i = 1; i <= 4; i++){
//			for(int j = 1; j <= 4; j++)
//				printf("%d ", top.G[i][j]);
//			puts("");	
//		}
//		puts("");
//		getchar();
		if(top.Check())	ans = min(ans, top.cnt);
		for(int i = 1; i <= 4; i++){
			for(int j = 1; j <= 4; j++){
				Array tmp; tmp.clear();
				memcpy(tmp.G, top.G, sizeof(top.G));
				tmp.cnt = top.cnt+1;
				tmp.Change(i, j);
				if(appear[tmp.Binary()])	continue;
				else Q.push(tmp), appear[tmp.Binary()] = 1;		
			}
		}
	}
	
	if(ans == 0x3f3f3f3f)	puts("Impossible");
	else		printf("%d\n", ans);

	END:
	fclose(stdin); fclose(stdout);
	return 0;
}
/*
bwwb 
bbwb 
bwwb 
bwww

4
*/