记录编号 |
287996 |
评测结果 |
AAAAAAAAAAAAAAAAAAAA |
题目名称 |
[NOIP 2010冲刺七]翻转游戏 |
最终得分 |
100 |
用户昵称 |
洛克索耶夫 |
是否通过 |
通过 |
代码语言 |
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
*/