题目链接：
http://codeforces.com/contest/676/problem/D
题意：
如果两个相邻的格子都有对应朝向的门，则可以从一个格子到另一个格子，给你初始坐标xt，yt，终点坐标xm,ym，现在你可以选择在原地把地图上所有格子顺时针旋转90度；或者往上下左右走一格，问走到终点的最短路。
题解：
三维的bfs最短路，就是写起来比较麻烦。
#include<iostream> #include<cstring> #include<cstdio> #include<vector> #include<queue> #include<utility> using namespace std; const int maxn = 1111; int n, m; char str[4][maxn][maxn]; char mp[256],dir[256][4]; void get_mp(){ memset(mp, 0, sizeof(mp)); mp['+'] = '+'; mp['-'] = '|'; mp['|'] = '-'; mp['^'] = '>'; mp['>'] = 'v'; mp['v'] = '<'; mp['<'] = '^'; mp['L'] = 'U'; mp['U'] = 'R'; mp['R'] = 'D'; mp['D'] = 'L'; mp['*'] = '*'; memset(dir, 0, sizeof(dir)); dir['+'][0] = dir['+'][1] = dir['+'][2] = dir['+'][3] = 1; dir['-'][1]=dir['-'][3]=1; dir['|'][0]=dir['|'][2]=1; dir['^'][0]=1; dir['>'][1]=1; dir['v'][2]=1; dir['<'][3]=1; dir['L'][0]=dir['L'][1]=dir['L'][2]=1; dir['U'][1]=dir['U'][2]=dir['U'][3]=1; dir['R'][0]=dir['R'][2]=dir['R'][3]=1; dir['D'][0] = dir['D'][1] = dir['D'][3] = 1; } struct Node { int s, x, y; Node(int s, int x, int y) :s(s), x(x), y(y) {} Node() {} }; int xt, yt, xm, ym; int d[4][maxn][maxn]; int vis[4][maxn][maxn]; int bfs() { memset(d, 0x3f, sizeof(d)); memset(vis, 0, sizeof(vis)); d[0][xt][yt] = 0; queue<Node> Q; Q.push(Node(0, xt, yt)); vis[0][xt][yt] = 1; while (!Q.empty()) { Node nd = Q.front(); Q.pop(); int s = nd.s, x = nd.x, y = nd.y; if (x == xm&&y == ym) return d[s][x][y]; int ss, xx, yy; ss = (s + 1) % 4, xx = x, yy = y; if (!vis[ss][xx][yy]) { d[ss][xx][yy] = d[s][x][y] + 1; Q.push(Node(ss, xx, yy)); vis[ss][xx][yy] = 1; } ss = s, xx = x - 1, yy = y; if (!vis[ss][xx][yy]&&xx>=1&&dir[str[ss][xx][yy]][2]&&dir[str[s][x][y]][0]) { d[ss][xx][yy] = d[s][x][y] + 1; Q.push(Node(ss, xx, yy)); vis[ss][xx][yy] = 1; } ss = s, xx = x + 1, yy = y; if (!vis[ss][xx][yy] && xx <=n && dir[str[ss][xx][yy]][0] && dir[str[s][x][y]][2]) { d[ss][xx][yy] = d[s][x][y] + 1; Q.push(Node(ss, xx, yy)); vis[ss][xx][yy] = 1; } ss = s, xx = x, yy = y-1; if (!vis[ss][xx][yy] && yy >= 1 && dir[str[ss][xx][yy]][1] && dir[str[s][x][y]][3]) { d[ss][xx][yy] = d[s][x][y] + 1; Q.push(Node(ss, xx, yy)); vis[ss][xx][yy] = 1; } ss = s, xx = x, yy = y + 1; if (!vis[ss][xx][yy] && yy <= m && dir[str[ss][xx][yy]][3] && dir[str[s][x][y]][1]) { d[ss][xx][yy] = d[s][x][y] + 1; Q.push(Node(ss, xx, yy)); vis[ss][xx][yy] = 1; } } return -1; } int main() { get_mp(); while (scanf("%d%d", &n, &m) == 2 && n) { for (int i = 1; i <= n; i++) scanf("%s", str[0][i]+1); for (int i = 1; i <= 3; i++) { for (int j = 1; j <= n; j++) { for (int k = 1; k <= m; k++) { str[i][j][k] = mp[str[i - 1][j][k]]; } } } scanf("%d%d%d%d", &xt, &yt, &xm, &ym); printf("%d ", bfs()); } return 0; }