【题意】：在一个迷宫里，有一个人，还有一个出口。这里有四种操作：1.人向左走 2.人向右走 3.把整个迷宫向左转 4.把整个迷宫向右转。每操作一次都会花费一个时间单位。问人最后能否走出迷宫？如果能，输出最短的时间。
【题解】：看到最短时间，我们很容易就想到bfs。这题与平时的迷宫问题有一个不同的地方就是，平时题目所给的迷宫是俯视图，而这里是主视图，考虑到这一点，我们就要把重力加入我们的思考范围。简单点来说就是，如果当前这个人向左走了一步，而那个位置是没有站块的，那么人就会向下跌，直到有东西顶住为止。实际操作的时候可以固定迷宫不动，而是通过人来旋转，这显然是可以的。一开始我们可以预处理一下对于每个格转动之后人会跌在哪里，这样我们以后就可以用O（1）的时间来找到下一个状态。其余的操作跟普通bfs一样。
【代码】：
1 #include "iostream"
2 #include "queue"
3 #include "cstdio"
4 using namespace std;
5 #define MAX 505
6 struct node {
7 int x, y, dir;
8 void init(int a, int b, int c) {
9 x = a, y = b, dir = c;
10 }
11 }rot[MAX][MAX][4], s;
12 int n, m;
13 int ti[MAX][MAX][4];
14 char maz[MAX][MAX];
15 const int dx[4] = {1, 0, -1, 0};
16 const int dy[4] = {0, 1, 0, -1};
17
18 bool check(int i, int j) {
19 if(i >= 1 && i <= n && j >= 1 && j <= m) return true;
20 return false;
21 }
22
23 int bfs() {
24 queue<node> que;
25 que.push(s);
26 ti[s.x][s.y][s.dir] = 1;
27 while(!que.empty()) {
28 node now = que.front(), next;
29 que.pop();
30 if(maz[now.x][now.y] == 'E') return ti[now.x][now.y][now.dir];
31 for(int i = 0; i < 4; i++) {
32 if((now.dir % 2 == 0 && i % 2 != 0) || (now.dir % 2 != 0 && i % 2 == 0)) {
33 if(maz[now.x+dx[i]][now.y+dy[i]] != '#') {
34 next = rot[now.x+dx[i]][now.y+dy[i]][now.dir];
35 if(!ti[next.x][next.y][next.dir]) {
36 ti[next.x][next.y][next.dir] = ti[now.x][now.y][now.dir] + 1;
37 que.push(next);
38 }
39 }
40 }
41 if(i % 2) {
42 next = rot[now.x][now.y][(now.dir + i) % 4];
43 if(!ti[next.x][next.y][next.dir]) {
44 ti[next.x][next.y][next.dir] = ti[now.x][now.y][now.dir] + 1;
45 que.push(next);
46 }
47 }
48 }
49 }
50 return 0;
51 }
52
53 void init() {
54 for(int i = n; i; i--)
55 for(int j = m; j; j--)
56 if(maz[i][j] != '#') {
57 if(check(i + 1, j) && maz[i+1][j] != '#') rot[i][j][0] = rot[i+1][j][0];
58 else rot[i][j][0].init(i, j, 0);
59 if(check(i, j + 1) && maz[i][j+1] != '#') rot[i][j][3] = rot[i][j+1][3];
60 else rot[i][j][3].init(i, j, 3);
61 }
62 for(int i = 1; i <= n; i++)
63 for(int j = 1; j <= m; j++)
64 if(maz[i][j] != '#') {
65 if(check(i - 1, j) && maz[i-1][j] != '#') rot[i][j][2] = rot[i-1][j][2];
66 else rot[i][j][2].init(i, j, 2);
67 if(check(i, j - 1) && maz[i][j-1] != '#') rot[i][j][1] = rot[i][j-1][1];
68 else rot[i][j][1].init(i, j, 1);
69 }
70 }
71
72 int main() {
73 while(~scanf("%d%d", &n, &m)) {
74 getchar();
75 for(int i = 1; i <= n; i++)
76 for(int j = 1; j <= m + 1; j++) {
77 for(int k = 0; k < 4; k++) ti[i][j][k] = 0;
78 scanf("%c", &maz[i][j]);
79 if(maz[i][j] == '|') s.init(i, j, 0);
80 }
81 init();
82 int ans = bfs();
83 if(!ans) printf("Can not escape!\n");
84 else printf("%d\n", ans - 1);
85 }
86 return 0;
87 }