【題意】：在一個迷宮里，有一個人，還有一個出口。這里有四種操作：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 }