BFS+状态压缩
这里用二进制去存状态，一共需要16位来存储，输入的时候顺便处理保存原始状态。当输入很长的时候可以分别写出来一个输入。其中位运算取反，注意要挪到哪一位做异或。
1 #include <iostream>
2 #include <fstream>
3 #include <cstdio>
4 #include <cstring>
5 #include <cmath>
6 #include <vector>
7 #include <map>
8 #include <queue>
9 #include <climits>
10 #include <algorithm>
11 using namespace std;
12 13 int st;
14 int dis[(1<<16) + 2];
15 16 bool get_input() {
17 char p;
18 for (
int i = 0; i < 16; ++i) {
19 int tmp = 0;
20 scanf("%c", &p);
21 if (p == '\n') {
22 --i;
23 continue;
24 }
25 if (p == 'b') tmp = 1;
26 st = st * 2 + tmp;
//输入的时候保存处理每一位的状态
27 }
28 return true;
29 }
30 31 void bfs() {
32 memset(dis, 0,
sizeof(dis));
33 queue<
int> q;
34 q.push(st);
35 if (st == 0 || st == (1<<16) - 1) {
36 printf("0\n");
37 return ;
38 }
39 while (!q.empty()) {
40 int sta = q.front();
41 q.pop();
42 for (
int i = 0; i < 16; ++i) {
43 int newsta = sta;
44 newsta ^= (1<<i);
45 if (i / 4 - 1 >= 0) newsta ^= (1<<(i - 4));
46 if (i / 4 + 1 <= 3) newsta ^= (1<<(i + 4));
47 if (i % 4 - 1 >= 0) newsta ^= (1<<(i - 1));
48 if (i % 4 + 1 <= 3) newsta ^= (1<<(i + 1));
49 50 if (dis[newsta] == 0) {
51 dis[newsta] = dis[sta] + 1;
52 q.push(newsta);
53 }
54 }
55 }
56 if ((dis[0] == 0) && (dis[(1<<16) - 1] == 0)) {
57 printf("Impossible\n");
58 return ;
59 }
60 if (dis[0] && dis[(1<<16) - 1]) {
61 printf("%d\n", max(dis[0], dis[(1<<16) - 1]));
62 return ;
63 }
64 if (dis[0] || dis[(1<<16) - 1]) {
65 printf("%d\n", max(dis[(1<<16) - 1], dis[0]));
66 }
67 }
68 69 70 int main() {
71 get_input();
72 bfs();
73 return 0;
74 }