題目意思很簡單，一個(gè)迷宮，問是否能夠從入口處進(jìn)入，在岔道口處向左拐，問采取這種策略能夠走到中心。
由于這里不是全DFS，而是具有某種優(yōu)先級(jí)順序，在這里，優(yōu)先級(jí)是指一直向左拐。
判重的時(shí)候不能僅僅判斷這個(gè)格子是否走過，還要加上方向向量，即從什么方向走入這個(gè)格子的。
1 # include <iostream>
2 # include <cstring>
3 # include <cstdio>
4 using namespace std;
5 char map[105][105];
6 bool used[105][105][4];//方向：0-向上 1-向右 2-向下 3-向左
7 int n,m;
8 int sr=-1,sc=-1;
9 inline bool chk(int r,int c)
10 {
11 if(r+1<n&&r-1>=0&&map[r+1][c]=='#'&&map[r-1][c]=='#') return true;
12 else if(c+1<m&&c-1>=0&&map[r][c-1]=='#'&&map[r][c+1]=='#') return true;
13 else return false;
14 }
15 inline int encode(int r,int c,int dir)
16 {
17 return (((r<<7)|c)<<2)|dir;
18 }
19 inline bool legal(int r,int c)
20 {
21 if(r>=0&&r<n&&c>=0&&c<m&&map[r][c]=='.') return true;
22 else return false;
23 }
24 void findstart(int r,int c)
25 {
26 if(r>=n||r<0||c>=m||c<0||map[r][c]!='.') return;
27 if(chk(r,c))
28 {
29 sr=r;
30 sc=c;
31 return;
32 }
33 map[r][c]=' ';
34 findstart(r+1,c);
35 findstart(r-1,c);
36 findstart(r,c+1);
37 findstart(r,c-1);
38 }
39 bool dfs(int r,int c,int dir)
40 {
41 // printf("%d %d %d\n",r,c,dir);
42 // system("pause");
43 if(used[r][c][dir]) return false;
44 else
45 {
46 if(legal(r,c)&&legal(r+1,c)&&legal(r,c+1)&&legal(r+1,c+1)||
47 legal(r,c-1)&&legal(r,c)&&legal(r+1,c-1)&&legal(r+1,c)||
48 legal(r-1,c)&&legal(r,c)&&legal(r-1,c+1)&&legal(r,c+1)||
49 legal(r-1,c-1)&&legal(r-1,c)&&legal(r,c-1)&&legal(r,c))
50 return true;
51 used[r][c][dir]=true;
52 switch(dir)
53 {
54 case 0:
55 if(legal(r,c-1)) return dfs(r,c-1,3);
56 else if(legal(r-1,c)) return dfs(r-1,c,0);
57 else if(legal(r,c+1)) return dfs(r,c+1,1);
58 break;
59 case 1:
60 if(legal(r-1,c)) return dfs(r-1,c,0);
61 else if(legal(r,c+1)) return dfs(r,c+1,1);
62 else if(legal(r+1,c)) return dfs(r+1,c,2);
63 break;
64 case 2:
65 if(legal(r,c+1)) return dfs(r,c+1,1);
66 else if(legal(r+1,c)) return dfs(r+1,c,2);
67 else if(legal(r,c-1)) return dfs(r,c-1,3);
68 break;
69 case 3:
70 if(legal(r+1,c)) return dfs(r+1,c,2);
71 else if(legal(r,c-1)) return dfs(r,c-1,3);
72 else if(legal(r-1,c)) return dfs(r-1,c,0);
73 break;
74 } ;
75 return false;
76 }
77
78 }
79 int main()
80 {
81 //int n,m;
82 scanf("%d%d",&n,&m);
83 for(int i=0;i<n;i++)
84 scanf("%s",map[i]);
85 for(int i=0;i<n;i++)
86 {
87 if(map[i][0]=='.')
88 findstart(i,0);
89 if(map[i][m-1]=='.')
90 findstart(i,m-1);
91 }
92 for(int i=0;i<m;i++)
93 {
94 if(map[0][i]=='.')
95 findstart(0,i);
96 if(map[n-1][i]=='.')
97 findstart(n-1,i);
98 }
99 // for(int i=0;i<n;i++)
100 // printf("%s\n",map[i]);
101 // system("pause");
102 memset(used,false,sizeof(used));
103 if(sr+1<n&&sr-1>=0&&map[sr+1][sc]=='#'&&map[sr-1][sc]=='#')
104 if(sc+1>=m||map[sr][sc+1]==' ')
105 printf("%s\n",dfs(sr,sc,3)?"YES":"NO");
106 else
107 printf("%s\n",dfs(sr,sc,1)?"YES":"NO");
108 else
109 if(sr+1>=n||map[sr+1][sc]==' ')
110 printf("%s\n",dfs(sr,sc,0)?"YES":"NO");
111 else
112 printf("%s\n",dfs(sr,sc,2)?"YES":"NO");
113 //system("pause");
114 return 0;
115
116 }
117