水两道搜索

#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;

int map[6][6];
int change[16] = { 51200, 58368, 29184, 12544, 35968, 20032, 10016, 4880, 2248,
        1252, 626, 305, 140, 78, 39, 19 };
int BFS(int state) {
    queue<pair<int, int> > Q;
    Q.push(make_pair(state, 0));
    int tmp;
    pair<int, int> cur;
    int vis[65536] = { 0 };
    while (!Q.empty()) {
        cur = Q.front();
        Q.pop();
        for (int i = 0; i < 16; i++) {
            tmp = cur.first ^ change[i];
            if (tmp == 0 || tmp == 65535)
                return cur.second + 1;
            if (!vis[tmp])
                Q.push(make_pair(tmp, cur.second + 1)), vis[tmp] = 1;
        }
    }
    return -1;
}
int main() {
//    freopen("data.txt", "r", stdin);
    char tmp;
    while (~scanf("%c", &tmp)) {
        int state = 0;
        memset(map, 0, sizeof(map));
        map[1][1] = (tmp == ‘b‘) ? 1 : 0;
        if (map[1][1])
            state += 1;
        for (int i = 1; i < 4; i++) {
            scanf("%c", &tmp);
            map[1][i] = (tmp == ‘b‘) ? 1 : 0;
            if (map[1][i])
                state += 1 << i;
        }
        for (int i = 2; i <= 4; i++) {
            getchar();
            for (int j = 1; j <= 4; j++) {
                scanf("%c", &tmp);
                map[i][j] = (tmp == ‘b‘) ? 1 : 0;
                if (map[i][j])
                    state += 1 << ((i - 1) * 4 + j - 1);
            }
        }
        getchar();
        if (state == 0 || state == 65535) {
            puts("0");
            continue;
        }
        int ans = BFS(state);
        ans == -1 ? puts("Impossible") : printf("%d\n", ans);
    }
    return 0;
}

#include <iostream>
#include <cstdio>
using namespace std;

int chess;
int step;
bool flag = false;
int ans_r[16], ans_c[16];

void flip(int bit) {
    int row = bit / 4;
    int col = bit % 4;
    for (int c = 0; c < 4; c++)
        chess = chess ^ (1 << (row * 4 + c));
    for (int r = 0; r < 4; r++)
        chess = chess ^ (1 << (r * 4 + col));
    chess = chess ^ (1 << bit);
    return;
}

void dfs(int bit, int deep) {
    if (deep == step) {
        flag = (chess == 65535) ? 1 : 0;
        return;
    }
    if (flag || bit > 15)
        return;
    ans_r[deep] = bit / 4;
    ans_c[deep] = bit % 4;

    flip(bit);
    dfs(bit + 1, deep + 1);
    flip(bit);
    dfs(bit + 1, deep);
    return;
}

int main(void) {
//    freopen("data.txt", "r", stdin);
    char tmp;
    for (int i = 0; i < 4; i++)
        for (int j = 0; j < 4; j++) {
            scanf("%c", &tmp);
            if (tmp == ‘-‘)
                chess ^= (1 << (i * 4 + j));
        }
    for (step = 0;; step++) {
        dfs(0, 0);
        if (flag)
            break;
    }
    printf("%d\n", step);
    for (int i = 0; i < step; i++)
        printf("%d %d\n", ans_r[i] + 1, ans_c[i] + 1);
    return 0;
}