【題意】：一個迷宮，有一個入口和出口。一個人想從入口進來，然后到達出口，又從出口進來，回到入口。但是他害怕走不出迷宮，于是他想到了一種走的方法：1.優先靠右邊走，能向右轉的都向右轉 2.不能靠右走的話就選擇直走 3.右走和直走都不能走的話選擇向左走 4.前面三種都不能走的話向后走。題目保證肯定存在一條從入口到出口的路，然后人必須按照上述的方法走迷宮。問最后，人能否把迷宮每個格子都走一遍？

【題解】：題目明顯就是讓你搜索的，對于每個格子i,j加多一維記錄方向就好了。由于數據最大是500*500，所以用系統棧會爆掉，改成非遞歸即可。如果你深一層理解題目的話，會發現是不需要用棧的，只需要一個循環就可以了，直接上代碼了，大家不懂再問吧。

【代碼】：
 1 #include <iostream>
 2 #include <cstdio>
 3 using namespace std;
 4 #define MAX 505
 5 
 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 } s, t, goal;
12 int r, c, n, m;
13 int maz[MAX][MAX][4];
14 bool visit[MAX][MAX];
15 const int dx[] = {0, 1, 0, -1};
16 const int dy[] = {1, 0, -1, 0};
17 
18 void dfs(node now, node goal) {
19     node next;
20     while (1) {
21         visit[now.x][now.y] = true;
22         if (now.x == goal.x && now.y == goal.y && now.dir == goal.dir) break;
23         for (int i = now.dir; i < 4 + now.dir; i++) {
24             int index = (now.dir - (i - now.dir) + 4) % 4;
25             if (maz[now.x][now.y][(now.dir - (i - now.dir) + 5) % 4] == 0) {
26                 next.init(now.x + dx[index], now.y + dy[index], (now.dir - (i - now.dir) + 5) % 4);
27                 now = next;
28                 break;
29             }
30         }
31     }
32 }
33 
34 void init() {
35     for (int i = 1; i <= r; i++)
36         for (int j = 1; j <= c; j++) {
37             visit[i][j] = false;
38             for (int k = 0; k < 4; k++)
39                 maz[i][j][k] = 1;
40         }
41         maz[t.x][t.y][s.dir] = maz[s.x][s.y][t.dir] = 0;
42 }
43 
44 int main() {
45     int T;
46     scanf("%d", &T);
47     while (T--) {
48         scanf("%d%d", &r, &c);
49         scanf("%d%d", &s.y, &t.y);
50         s.init(1, s.y + 1, 2), t.init(r, t.y + 1, 0);
51         init();
52         for (int i = 1; i < 2 * r; i++) {
53             if (i % 2 != 0) {
54                 for (int j = 1; j < c; j++) {
55                     scanf("%d", &maz[(i + 1) / 2][j][1]);
56                     maz[(i + 1) / 2][j + 1][3] = maz[(i + 1) / 2][j][1];
57                 }
58             } else {
59                 for (int j = 1; j <= c; j++) {
60                     scanf("%d", &maz[i / 2][j][2]);
61                     maz[i / 2 + 1][j][0] = maz[i / 2][j][2];
62                 }
63             }
64         }
65         goal.init(t.x + 1, t.y, s.dir);
66         dfs(s, goal);
67         goal.init(s.x - 1, s.y, t.dir);
68         dfs(t, goal);
69         bool flag = false;
70         for (int i = 1; i <= r; i++)
71             for (int j = 1; j <= c; j++)
72                 if (!visit[i][j])
73                     flag = true;
74         if (!flag) printf("YES\n");
75         else printf("NO\n");
76     }
77     return 0;
78 }