左手定则
题目描述
玩过RPG（尤其是国产RPG）的童鞋都应该对迷宫这种神棍的设定深恶痛绝，尤其是当你转了半小时之后发现回到了原地，这种感觉真是无比的痛苦。。。万一游戏还中途崩溃了那真是连掀桌子、砸键盘、摔鼠标的心都有了……
经过无数次的TRIAL AND ERROR之后，玩家终于下定决心认定迷宫存在的意义就是延长游戏时间，SO，他决定借鉴著名的左手定则（就是在每一个路口，我们都选择最左边的方向，左转的优先级最高，其次为向前，最后为右转，如果实在走进了一个死胡同，那就连续右转两次，回头向后走。稍微研究一下这种走迷宫的方法，我们就发现在这个过程中，事实上我们的左手可以始终放在墙上。）对迷宫进行探索。
但是呢，左手定则并不能保证遍历到迷宫中的每一个点。悲剧的是，某项重要的通关道具被放在了这个迷宫中……幸运的是，游戏迷宫的地图可以绘制出来，现在请求你的帮助。对于一个给定的地图，他想知道是不是能够通过左手定则取得这件道具。
关于输入
多组数据。
对于每组数据，第一行有两个整数N,M代表接下来有n行字符串，每行m个字符，其中0 < n <= 100, 0 < m <= 100，表示一个n × m的迷宫。
其中‘#’表示墙，‘S’表示起点，‘T’表示道具，‘.’表示空地。
接下来是一个方向（NSWE），表示起始面向的方向。
数据保证最外一圈都是墙。
关于输出
对于每组数据输出一行。‘YES’表示可以到达，‘NO’表示无法到达。
例子输入
8 10 ########## #...T....# #.####...# #.#..#.#.# #.#....#.# #.####.#.# #......#S# ########## N 8 10 ########## #........# #.####...# #.#T.#.#.# #.#....#.# #.####.#.# #......#S# ########## N 8 10 ########## #....#...# #..#.#...# #..#.....# #..#.#S### #..#.#...# #....#T..# ########## N
例子输出
YES NO YES
提示信息
E东
S南
W西
N北
不会原地转圈
解题分析
这个问题可以用深度优先搜索(DFS)的实现，主要用于解决迷宫探索问题，特别是在迷宫中寻找特定的目标。在这个问题中，我们使用了左手定则，即在每个路口，我们都选择最左边的方向，左转的优先级最高，其次为向前，最后为右转，如果实在走进了一个死胡同，那就连续右转两次，回头向后走。
要解决的问题：
1. **迷宫和访问状态的存储**
```c
char maze[105][105];
int visited[105][105][4] = {0};
```
`maze[105][105]` 是一个二维字符数组，用于存储迷宫的地图。迷宫中的墙壁由字符 '#' 表示，起点由 'S' 表示，目标（道具）由 'T' 表示，空地由 '.' 表示。
`visited[105][105][4]` 是一个三维整数数组，用于记录在四个方向（北、东、南、西）上每个位置是否被访问过。通过这个数组，我们可以避免在搜索过程中重复访问同一位置的同一方向。
2. **方向的表示**
```c
int dp[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
```
`dp[4][2]` 是一个二维整数数组，用于表示四个方向（北、东、南、西）的位移。数组的第一维代表方向，第二维代表在 x 和 y 方向上的位移。例如，`{-1, 0}` 代表向北移动，`{0, 1}` 代表向东移动，`{1, 0}` 代表向南移动，`{0, -1}` 代表向西移动。
3. **位置的更新**
```c
void change(int *x, int *y, int dir, int dir_to){
*x += dp[(dir + dir_to + 4) % 4][0];
*y += dp[(dir + dir_to + 4) % 4][1];
}
```
`change` 函数用于根据当前的方向和要转向的方向，更新当前的位置。这里使用了 `(dir + dir_to + 4) % 4` 来计算新的方向，模4是为了循环0-3，这里注意与dp数组移动坐标相对应，只需举一个例子向北，然后就可以根据这个例子去确定方向和表示，然后通过 `dp` 数组来获取在 x 和 y 方向上的位移。
4. **深度优先搜索**
```c
int dfs(int x, int y, int dir){
...
for(int i = -1; i < 3; i++){
int dx = x, dy = y;
change(&dx, &dy, dir, i);
...
if(maze[dx][dy] != '#'){
visited[dx][dy][(dir + i + 4) % 4] = 1;
return dfs(dx, dy, (dir + i + 4) % 4);
}
}
...
}
```
`dfs` 函数是一个深度优先搜索函数，它会尝试从当前位置向四个方向移动，并且优先选择左边的方向。如果找到了道具，就返回1，表示可以到达；如果四个方向都尝试过了还没找到道具，就返回0，表示无法到达。在这个函数中，我们使用了 `change` 函数来更新位置，并使用了 `visited` 数组来记录访问状态。
5. **主函数**
```c
int main() {
...
if(dfs(xi, yi, Dir0)) printf("YES\n");
else printf("NO\n");
...
}
```
`main` 函数首先读取输入数据，然后调用 `dfs` 函数进行搜索。如果 `dfs` 函数返回1，就输出 'YES'，表示可以通过左手定则找到道具；如果 `dfs` 函数返回0，就输出 'NO'，表示无法通过左手定则找到道具。
这个程序的主要思路是，我们始终尝试向左边的方向移动，如果左边的方向是墙，就尝试向前移动，如果前面也是墙，就尝试向右移动，如果右边也是墙，就回头。这样，我们就可以遍历迷宫中的所有可能路径，而且不会重复绕圈圈。
代码实现
#include <stdio.h>
#include <string.h>
char maze[105][105];
int visited[105][105][4] = {0};
int dp[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
int N, M;
void change(int *x, int *y, int dir, int dir_to){
*x += dp[(dir + dir_to + 4) % 4][0];
*y += dp[(dir + dir_to + 4) % 4][1];
}
int dfs(int x, int y, int dir){
if(maze[x][y] == 'T'){
return 1;
}
for(int i = -1; i < 3; i++){
int dx = x, dy = y;
change(&dx, &dy, dir, i);
if(dx >= 0 && dx < N && dy >= 0 && dy < M){
if(visited[dx][dy][(dir + i + 4) % 4]) return 0;
else if(maze[dx][dy] != '#'){
visited[dx][dy][(dir + i + 4) % 4] = 1;
return dfs(dx, dy, (dir + i + 4) % 4);
}
}
}
return 0;
}
int main() {
int xi, yi;
while(scanf("%d %d", &N, &M) != EOF){
memset(visited, 0, sizeof(visited));
getchar(); // 吸收换行符
for(int i = 0; i < N; i++){
for(int j = 0; j < M; j++){
scanf(" %c", &maze[i][j]); // 注意%c前的空格，用于吸收空白字符
if(maze[i][j] == 'S'){
xi = i; yi = j;
}
}
}
char firstDir;
int Dir0;
scanf(" %c", &firstDir); // 注意%c前的空格
switch(firstDir){
case 'N':
Dir0 = 0;
break;
case 'E':
Dir0 = 1;
break;
case 'S':
Dir0 = 2;
break;
case 'W':
Dir0 = 3;
break;
}
if(dfs(xi, yi, Dir0)) printf("YES\n");
else printf("NO\n");
}
return 0;
}
进一步拓展
在使用 scanf("%c", &maze[i][j]); 读取字符时，%c 会读取所有字符，包括空格、制表符和换行符。这意味着如果在输入中有任何空白字符（如输入两个字符之间的空格或上一个输入后的换行符），%c 会将其作为有效字符读取，这可能会导致输入不符合预期。
为了避免这个问题，scanf(" %c", &maze[i][j]); 中的空格告诉 scanf 忽略所有标准空白字符（空格、制表符、换行符等），直到遇到第一个非空白字符。这样，它只会读取并存储真正的有效字符，而忽略所有前导的空白字符。
例如，在读取矩阵或字符网格时，这种处理方式尤其重要，因为它确保了只有实际的数据字符（非空白字符）被读取并存储在数组中。
