大概的看了下思路，以后再写吧
神奇的三个点bfs
题目大意：在一张图中，以最少的步数将a,b,c移到对应的A,B,C上去。其中，每个2x2的方格都有障碍并且不能两个小写字母同时占据一个格子。
题目分析：为避免超时，先将图中所有能联通的空格建起一张图，然后再BFS。
听说双端很快，但是不想动......
考试遇到了再说吧，网上找的代码：
#include <bits/stdc++.h> using namespace std; #define N 20 typedef pair<int, int> P; #define f first #define s second struct node ///状态节点 { int a, b, c; node(int a1 = 0, int b1 = 0, int c1 = 0):a(a1), b(b1), c(c1) {} bool operator == (const node & d)const { return a == d.a && b == d.b && c == d.c; } bool operator < (const node & d)const { if(a != d.a) return a < d.a; if(b != d.b) return b < d.b; if(c != d.c) return c < d.c; return true; } }; int w, h, n; ///当前距离 int d[N * N][N * N][N * N]; char maze[N][N]; int dx[] = {0, 0, -1, 1, 0}; int dy[] = {1, -1, 0, 0, 0}; ///大小写字母 P low[3], up[3]; int lo, lu; vector<int> space[N * N]; bool cmp(const P & a, const P & b) { return maze[a.f][a.s] < maze[b.f][b.s]; } inline int getid(int i, int j) { return (i - 1) * w + j; } node getmp(P & a, P & b, P & c) { node ans; ans.a = getid(a.f, a.s); ans.b = getid(b.f, b.s); ans.c = getid(c.f, c.s); return ans; } bool conflict(const node & nd, int ida, int idb, int idc) { //cout << ida <<' ' << idb << ' ' << idc<< endl; if(nd.a == idb && nd.b == ida)return true; if(nd.c == idb && nd.b == idc)return true; if(nd.a == idc && nd.c == ida)return true; if(ida == idb || ida == idc || idc == idb) return true; return false; } int bfs() { node start = getmp(low[0], low[1], low[2]); memset(d, -1, sizeof d); if(n <= 2) start.c = 1000; if(n == 1) start.b = 2000; d[start.a][start.b][start.c] = 0; queue<node> que; que.push(start); node goal = getmp(up[0], up[1], up[2]); if(n <= 2) goal.c = 1000; if(n == 1) goal.b = 2000; while(!que.empty()) { node h = que.front(); que.pop(); if(h == goal) return d[h.a][h.b][h.c]; if(n == 3) for(int i = 0; i < space[h.a].size(); i++) { for(int j = 0; j < space[h.b].size(); j++) { if(!conflict(h, space[h.a][i], space[h.b][j], 1000)) for(int k = 0; k < space[h.c].size(); k++) { if( conflict(h, space[h.a][i], space[h.b][j], space[h.c][k]) ) continue; if(d[space[h.a][i]][space[h.b][j]][space[h.c][k]] != -1) continue; d[space[h.a][i]][space[h.b][j]][space[h.c][k]] = d[h.a][h.b][h.c] + 1; que.push(node(space[h.a][i], space[h.b][j], space[h.c][k])); } } } else if(n == 2) for(int i = 0; i < space[h.a].size(); i++) { for(int j = 0; j < space[h.b].size(); j++) { if( conflict(h, space[h.a][i], space[h.b][j], 1000) ) continue; if(d[space[h.a][i]][space[h.b][j]][1000] != -1) continue; d[space[h.a][i]][space[h.b][j]][1000] = d[h.a][h.b][1000] + 1; que.push(node(space[h.a][i], space[h.b][j], 1000)); //cout << "AAA" << endl; } } else for(int i = 0; i < space[h.a].size(); i++) { if( conflict(h, space[h.a][i], 2000,1000) ) continue; if(d[space[h.a][i]][2000][1000] != -1) continue; d[space[h.a][i]][2000][1000] = d[h.a][2000][1000] + 1; que.push(node(space[h.a][i], 2000,1000)); //cout << "AAA" << endl; } } return -1; } int main() { while(scanf("%d%d%d", &w, &h, &n) && w + h + n) { getchar(); for(int i = 1; i < N * N; i++)space[i].clear(); lo = lu = 0; for(int i = 1; i <= h; i++) { maze[i][0] = '#'; for(int j = 1; j <= w; j++) { maze[i][j] = getchar(); } maze[i][w + 1] = ' '; getchar(); } int id, x, y; for(int i = 1; i <= h; i++) { for(int j = 1; j <= w; j++) { if(maze[i][j] != '#') { id = getid(i, j), x, y; for(int k = 0; k < 5; k++) { x = i + dx[k], y = j + dy[k]; if(0 < x && x <= h && 0 < y && y <= w && maze[x][y] != '#') { space[id].push_back(getid(x, y)); } } } if('a' <= maze[i][j] && maze[i][j] <= 'z') { low[lo].f = i; low[lo].s = j; lo++; } else if('A' <= maze[i][j] && maze[i][j] <= 'Z') { up[lu].f = i; up[lu].s = j; lu++; } } } sort(low, low + lo, cmp); sort(up, up + lu, cmp); printf("%d ", bfs()); } return 0; }