比赛 |
20121009 |
评测结果 |
AAAAAAAAWAWAAAAAAAAA |
题目名称 |
翻转游戏 |
最终得分 |
90 |
用户昵称 |
万里长城 |
运行时间 |
0.051 s |
代码语言 |
C++ |
内存使用 |
3.15 MiB |
提交时间 |
2012-10-09 21:44:13 |
显示代码纯文本
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define clr(x, n) memset(x, n, sizeof(x))
#define inf 0x7fffffff
using namespace std;
void setIO(string name) {
string in_f = name + ".in";
string out_f = name + ".out";
freopen(in_f.c_str(), "r", stdin);
freopen(out_f.c_str(), "w", stdout);
}
bool bl[4][4];
int ans, num;
void init() {
ans = inf;
num = 0;
char ch;
rep(i, 4) rep(j,4) {
scanf(" %c", &ch);
if (ch == 'w') bl[i][j] = 0;
else bl[i][j] = 1;
}
}
bool pd() {
bool t = bl[0][0];
rep(i, 4) rep(j, 4) {
if (t != bl[i][j]) return false;
}
return true;
}
void click(int x, int y) {
bl[x][y] = !bl[x][y];
if (x > 0) bl[x - 1][y] = !bl[x - 1][y];
if (x < 3) bl[x + 1][y] = !bl[x + 1][y];
if (y > 0) bl[x][y - 1] = !bl[x][y - 1];
if (y < 3) bl[x][y + 1] = !bl[x][y + 1];
}
void dfs(int x, int y) {
if (pd()) {
if (num < ans) ans = num;
return;
}
click(x, y);
num++;
if (y < 3) dfs(x, y + 1);
else if (x < 3) dfs(x + 1, 0);
click(x, y);
num--;
if (y < 3) dfs(x, y + 1);
else if (x < 3) dfs(x + 1, 0);
}
void solve() {
dfs(0, 0);
if (ans != inf) printf("%d\n", ans);
else printf("Impossible\n");
}
int main() {
setIO("flip");
init();
solve();
return 0;
}