https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4476
题意：给出w*h的网格，相当于迷宫，有大写字母和小写字母，算出小写字母走到大写字母状态时的最少步数。
思路：建立新图，然后再bfs。
1 #include<iostream> 2 #include<string> 3 #include<cstring> 4 #include<queue> 5 using namespace std; 6 7 const int maxn = 16 * 16; 8 9 char map[20][20]; 10 int w, h, n; 11 int cnt; //非#结点个数 12 int x[maxn], y[maxn]; 13 int s[3], t[3]; //记录初末位置 14 int deg[maxn]; //记录每个格子相连的格子数 15 int G[maxn][maxn]; //记录每个格子可以走的位置 16 int new_map[20][20]; //新图 17 int d[maxn][maxn][maxn]; //记录步数 18 19 int dx[] = { 0, 1, -1, 0, 0 }; 20 int dy[] = { 0, 0, 0, 1, -1 }; 21 22 int ID(int x, int y, int z) //二进制压缩存储，方便进出队列 23 { 24 return (x << 16) | (y << 8) | z; 25 } 26 27 bool judge(int a, int b, int a2, int b2) 28 { 29 return a2 == b2 || (a2 == b && b2 == a); 30 } 31 32 void bfs() 33 { 34 queue<int> q; 35 memset(d, -1, sizeof(d)); 36 q.push(ID(s[0], s[1], s[2])); //二进制压缩后再进队 37 d[s[0]][s[1]][s[2]] = 0; 38 while (!q.empty()) 39 { 40 int u = q.front(); 41 q.pop(); 42 int a = (u >> 16) & 0xff; //得到压缩前的数据 43 int b = (u >> 8) & 0xff; 44 int c = u & 0xff; 45 if (a==t[0] && b==t[1] && c==t[2]) //得到目标状态 46 { 47 cout << d[a][b][c] << endl; 48 return; 49 } 50 for (int i = 0; i < deg[a]; i++) 51 { 52 int a2 = G[a][i]; 53 for (int j = 0; j < deg[b]; j++) 54 { 55 int b2 = G[b][j]; 56 if (judge(a, b, a2, b2)) continue; //删去不符合条件的走法 57 for (int k = 0; k < deg[c]; k++) 58 { 59 int c2 = G[c][k]; 60 if (judge(a, c, a2, c2)) continue; 61 if (judge(b, c, b2, c2)) continue; 62 if (d[a2][b2][c2] != -1) continue; 63 d[a2][b2][c2] = d[a][b][c] + 1; 64 q.push(ID(a2, b2, c2)); 65 } 66 } 67 } 68 } 69 } 70 71 72 int main() 73 { 74 //freopen("D:\txt.txt", "r", stdin); 75 while (cin>>w>>h>>n && n) 76 { 77 getchar(); 78 cnt = 0; //记录非#结点个数 79 memset(map, 0, sizeof(map)); 80 memset(deg, 0, sizeof(deg)); 81 for (int i = 0; i < h; i++) 82 { 83 fgets(map[i], 20, stdin); 84 for (int j = 0; j < w; j++) 85 { 86 if (map[i][j] != '#') 87 { 88 x[cnt] = i; 89 y[cnt] = j; 90 new_map[i][j] = cnt; //建图记录结点 91 if (map[i][j] >= 'a' && map[i][j] <= 'c') s[map[i][j] - 'a'] = cnt; 92 if (map[i][j] >= 'A' && map[i][j] <= 'C') t[map[i][j] - 'A'] = cnt; 93 cnt++; 94 } 95 } 96 } 97 98 for (int i = 0; i < cnt; i++) 99 { 100 for (int k = 0; k < 5; k++) 101 { 102 int xx = x[i] + dx[k]; 103 int yy = y[i] + dy[k]; 104 if (map[xx][yy] != '#') G[i][deg[i]++] = new_map[xx][yy]; //如果可以走，则将第i个点的第deg[i]个方向的下一个格子记录 105 } 106 } 107 108 //如果不满三个鬼，强行添加结点使之构成三个结点 109 110 if (n <= 2) //添加虚拟结点 111 { 112 deg[cnt] = 1; G[cnt][0] = cnt; s[2] = t[2] = cnt++; 113 } 114 if (n <= 1) 115 { 116 deg[cnt] = 1; G[cnt][0] = cnt; s[1] = t[1] = cnt++; 117 } 118 119 bfs(); 120 } 121 return 0; 122 }