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