c++迷宫游戏（DFS实例）

题目背景：

我们用一个二维的字符数组来表示迷宫；其中字符 S 表示起点，字符 T 表示终点，字符 * 表示墙壁，字符 . 表示平地。你需要从S出发走到T，每次只能向上下左右相邻的位置移动，不能走出地图，也不能穿过墙壁，每个点只能通过一次。你需要编程来求解出一种从起点到终点的走法。

输入的第一行为两个整数，表示迷宫的行数和列数，中间用空格分开。下面每行为迷宫每行的样子。

要求输出从起点走到终点的路径，路径有字符 H 表示。

样例输入：

5 6

....S*

.***..

.*..*.

*.***.

.T....

样例输出：

.T....
....H*
.***HH
.*..*H
*.***H
.THHHH

示例代码：

#include
#include
using namespace std;
string maze[110];
int n, m;
bool vis[110][110];
int dir[4][2] = {{-1,0},{0,-1},{1,0},{0,1}};

bool in(int x, int y)
{
	if(x >= 0 && x < n && y >= 0 && y < m)
	{
		return true;
	}
	else
	{
		return false;
	}
}

bool dfs(int x, int y)
{
	if(maze[x][y] == 'T')
	{
		return true;
	}
	vis[x][y] = 1;
	maze[x][y] = 'H';
	for (int i = 0; i < 4; i++)
	{
		int tx = x + dir[i][0];
		int ty = y + dir[i][1];
		if(in(tx,ty) && maze[tx][ty] != '*' && !vis[tx][ty])   //注意这里的判断条件必须
		{                                                      //把in(tx,ty)写在最前面
			if(dfs(tx,ty))                                     //否则string数组会越界
			{
				return true;
			}
		}
	}
	vis[x][y] = 0;
	maze[x][y] = '.';
	return false;
}

int main()
{
	cin >> n >> m;
	for (int i = 0; i < n; i++)
	{
		cin >> maze[i];
	}
	int x, y;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			if(maze[i][j] == 'S')
			{
				x = i, y = j;
			}
		}
	}
	if(dfs(x,y))
	{
		for (int i = 0; i < n; i++)
		{
			cout << maze[i] << endl;
		}
	}
	else
	{
		cout << "NO!" << endl;
	}
	return 0;
}

运行截图：