有一个4x4的网格上面有16个按钮。按钮只有黑(b)白(w)两种颜色。按动任意一个按钮，那么该按钮本身以及其上下左右的按钮（如果有的话）都会改变颜色(由白变黑，由黑变白)。给出初始按钮的状态，输出最少要按多少次按钮才可以让所有按钮变为同一种颜色。
输入
输入有4行，每行包括4个字符（‘w’或’b’, ‘w’表示该位置目前为白色按钮，’b’表示该位置为黑色按钮）。
输出
输出最少要按多少次才能将所有的按钮变成同一颜色，如果没有办法变成相同颜色，输出Impossible。
样例
输入
复制
bwwb bbwb bwwb bwww
输出
复制
4
bfs,二进制。
#pragma warning(disable:4996) #include <iostream> #include <cstdio> #include <numeric> #include <cstring> #include <vector> #include <algorithm> #include <functional> #define inf 0x3f3f3f3f int main() { char ch[17]; for (int i = 0; i < 4; i++) { scanf("%s", ch + i * 4); } int start = 0; int state[16] = { 0 }; for (int i = 0; i < 16; i++) { if (ch[i] == 'b') { start |= 1 << i; } if (i - 4 >= 0) { state[i] |= 1 << (i - 4); } if (i + 4 < 16) { state[i] ^= 1 << (i + 4); } if (i % 4 != 0) { state[i] ^= 1 << (i - 1); } if (i % 4 != 3) { state[i] ^= 1 << (i + 1); } state[i] ^= 1 << i; } int vis[1 << 16]; int q[1 << 16]; int head = 0, tail = 0; int ones = (1 << 16) - 1; q[tail++] = 0; vis[0] = vis[ones] = 0; while (head < tail) { int top = q[head++]; for (int i = 0; i < 16; i++) { int next = top ^ state[i]; if (next && next != ones && !vis[next]) { vis[next] = vis[top] + 1; vis[ones - next] = vis[next]; q[tail ++] = next; if (next == start) { break; } } } } if (start == ones || !start || vis[start] != 0) printf("%d", vis[start]); else printf("Impossible"); return 0; } /* bwww wwww wwww wwww */