题目来源：http://poj.org/problem?id=1753
题目大意：给定一个4*4的黑白方阵，每次可使某一点及其上下左右相邻的四个点的颜色反转，问最小操作几次可使整个方阵变为全为黑色或全为白色。
状态压缩bfs。由于最多有2^16-1=65535种状态，只需使用一个vis数组来判重即可。
代码：
#include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <algorithm> #include <iostream> #include <iomanip> #include <string> #include <vector> #include <queue> #include <map> #include <set> #define ll long long #define ull unsigned long long #define BUG cout<<"*************************"<<endl using namespace std; const ll mod = 998244353; const int maxn = 1e5 + 10; const int maxm = 1e6 + 10000; const double eps = 1e-8; int a[5][5]; bool vis[2000000]; int change() { int pos = 0; for (int i = 1; i <= 4; i++) { for (int j = 1; j <= 4; j++) { if (a[i][j] == 1) { int c = (i - 1) * 4 + j; pos = (pos | (1 << (c - 1))); } } } return pos; } void back(int pos) { for (int i = 1; i <= 4; i++) { for (int j = 1; j <= 4; j++) { int c = (i - 1) * 4 + j; if (pos & (1 << (c - 1)))a[i][j] = 1; else a[i][j] = 0; } } } int main() { ios::sync_with_stdio(false); memset(vis, 0, sizeof(vis)); for (int i = 1; i <= 4; i++) { for (int j = 1; j <= 4; j++) { char c; cin >> c; if (c == 'b')a[i][j] = 1; else a[i][j] = 0; } } int pos = change(); vis[pos] = 1; queue<int> q, p; q.push(pos); int tot = 0; bool ok = 0; while (!q.empty()) { int x = q.front(); q.pop(); if (x == 0 || x == 65535) { ok = 1; break; } back(x); for (int i = 1; i <= 4; i++) { for (int j = 1; j <= 4; j++) { a[i][j] = 1 - a[i][j]; if (i - 1 >= 1)a[i - 1][j] = 1 - a[i - 1][j]; if (i + 1 <= 4)a[i + 1][j] = 1 - a[i + 1][j]; if (j - 1 >= 1)a[i][j - 1] = 1 - a[i][j - 1]; if (j + 1 <= 4)a[i][j + 1] = 1 - a[i][j + 1]; int e = change(); if (vis[e] == 0) { vis[e] = 1; p.push(e); } a[i][j] = 1 - a[i][j]; if (i - 1 >= 1)a[i - 1][j] = 1 - a[i - 1][j]; if (i + 1 <= 4)a[i + 1][j] = 1 - a[i + 1][j]; if (j - 1 >= 1)a[i][j - 1] = 1 - a[i][j - 1]; if (j + 1 <= 4)a[i][j + 1] = 1 - a[i][j + 1]; } } if (q.empty()) { tot++; swap(p, q); } } if (ok)cout << tot; else cout << "Impossible"; return 0; }
