【BNUOJ 4358】左手定则

描述：

玩过RPG（尤其是国产RPG）的童鞋都应该对迷宫这种神棍的设定深恶痛绝，尤其是当你转了半小时之后发现回到了原地，这种感觉真是无比的痛苦。。。万一游戏还中途崩溃了那真是连掀桌子、砸键盘、摔鼠标的心都有了……
经过无数次的TRIAL AND ERROR之后，玩家终于下定决心认定迷宫存在的意义就是延长游戏时间，SO，他决定借鉴著名的左手定则（就是在每一个路口，我们都选择最左边的方向，左转的优先级最高，其次为向前，最后为右转，如果实在走进了一个死胡同，那就连续右转两次，回头向后走。稍微研究一下这种走迷宫的方法，我们就发现在这个过程中，事实上我们的左手可以始终放在墙上。）对迷宫进行探索。
但是呢，左手定则并不能保证遍历到迷宫中的每一个点。悲剧的是，某项重要的通关道具被放在了这个迷宫中……幸运的是，游戏迷宫的地图可以绘制出来，现在请求你的帮助。对于一个给定的地图，他想知道是不是能够通过左手定则取得这件道具。

输入：

多组数据。
对于每组数据，第一行有两个整数N,M代表接下来有n行字符串，每行m个字符，其中0<n<=100,0<m<=100，表示一个n×m的迷宫。 <br="">其中‘#’表示墙，‘S’表示起点，‘T’表示道具，‘.’表示空地。
接下来是一个方向（NSWE），表示起始面向的方向。
数据保证最外一圈都是墙。

输出：

对于每组数据输出一行。‘YES’表示可以到达，‘NO’表示无法到达。

 1 #include<iostream>
 2 #include<cstring>
 3 using namespace std;
 4 int n,m,sx,sy,v[205][205][4];
 5 int ss[26],d[4][2]={-1,0,0,1,1,0,0,-1}; //x和y是哪个要明白....(因为这个WA很多次
 6 char dir,maze[205][205];
 7 void trans(int &x,int &y,int dirc,int dir_to){
 8     x+=d[(dirc+dir_to+4)%4][0];
 9     y+=d[(dirc+dir_to+4)%4][1];
10 }
11 int dfs(int x,int y,int dirc){
12     if(maze[x][y]=='T') return 1;
13     for(int i=-1;i<3;i++){
14         int dx=x,dy=y;
15         trans(dx,dy,dirc,i);
16         if(v[dx][dy][(dirc+i+4)%4]) return 0;
17         if(maze[dx][dy]!='#'&&!v[dx][dy][(dirc+i+4)%4]){
18             v[dx][dy][(dirc+i+4)%4]=1;
19             return dfs(dx,dy,(dirc+i+4)%4);
20         }
21     }
22     return 0;
23 }
24 int main()
25 {
26     ss['N'-'A']=0;
27     ss['E'-'A']=1; 
28     ss['S'-'A']=2; 
29     ss['W'-'A']=3;  
30     while(cin>>n>>m){
31         for(int i=0;i<n;i++)
32             for(int j=0;j<m;j++){
33                 cin>>maze[i][j];
34                 if(maze[i][j]=='S') sx=i,sy=j;
35             } 
36         cin>>dir;
37         memset(v,0,sizeof v);
38         if(dfs(sx,sy,ss[dir-'A'])) printf("YES
");
39         else printf("NO
");
40     }
41 }

【BNUOJ 4358】 左手定则

【BNUOJ 4358】左手定则