按步补充代码

#include <iostream>
#include <string>
using namespace std;
int n, m;
string maze[110];
int sx, sy;
bool vis[110][110];
bool in(int x, int y) {
    return 0 <= x && x < n && 0 <= y && y < m;
}
bool dfs(int x, int y) {
  
}
int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> maze[i];
    }
  
    if (dfs(sx, sy)) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}

在这个题目中，我们需要完成对迷宫问题的求解。

我们已经定义好了dfs函数，在这个函数中有两个参数，分别是 当前状态 的横坐标和纵坐标。在初始的时候这两个参数的值应该是起点的横坐标和纵坐标，之后随着搜索过程的进行，函数的参数也会进行相应的变换。

这个函数的返回值应该为bool类型，代表能否从起始点走到目标点。

第一步：首先，我们应该找到起始点的坐标点。

在main函数中，我们已经读入了整个迷宫，存在maze数组中。maze是一个字符串数组，从maze[0]到maze[n - 1]代表了迷宫的每一行。接下来我们要去迷宫中找到起始坐标点，把起始坐标保存在sx和sy两个变量里。

在main函数完成读入的部分后写下:

for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
        if (maze[i][j] == 'S') {
            sx = i;
            sy = j;
        }
    }
}

---

接下来，我们要完成dfs函数。

在dfs的过程中，我们首先要做的事情，是标记当前状态，也是当前经过的点为访问过，然后判断当前状态是否为终点。如果当前状态为终点，很明显我们应该直接返回true。

在dfs函数中写下：

vis[x][y] = true;
if (maze[x][y] == 'T') {
	return true;
}

---

第三步，我们继续完成dfs函数。

如果当前状态不是终点，那么我们就要依次搜索它的四个相邻点。如果相邻点合法，那么我们就要递归的调用dfs函数去搜索它的相邻点。因此我们先把相邻点坐标求出来。按照我们之前课上讲的，我们每一次算出一个相邻点坐标然后进去搜索，会发现代码有太多重复的部分了，想一想怎么简化重复代码。

一般重复代码可以考虑用循环来简化，那我们可以声明出一个数组表示 4 个方向，用循环扫描这 4 个方向，算出每个相邻点，然后进行搜索。

先声明好这个方向数组，在in函数前边写下：

int dir[4][2] = { { 1, 0}, {-1, 0}, {0, 1}, {0, -1}};

这个二维数组每一行就是一个方向，每一行第一个数是横坐标的变化，第二个数是纵坐标的变化。

---

第四步：使用循环扫描这 4 个方向，每一次计算出这一次考虑的相邻点(tx, ty)。

在dfs函数中继续写下:

for (int i = 0; i < 4; i++) {
    int tx = x + dir[i][0];
    int ty = y + dir[i][1];
  
}

---

第五步：我们要判断(tx, ty)是否合法。合法包括三个要素: 必须在所给定的迷宫范围内。 、 这个点在本次搜索中必须没有被访问过。 、这个点必须不是墙壁。

我们通过已经写好的in函数判断是不是在所给定的迷宫范围内，用vis数组判断是不是在搜索中被访问过，然后根据maze[tx][ty]的值判断这个点是不是墙壁。

如果这个点合法，就递归搜索，如果这个点可以到终点那我们现在所在的点也就可以到终点了，就直接返回true。

在dfs函数的for循环中继续写下

if (in(tx, ty) && !vis[tx][ty] && maze[tx][ty] != '*') {
    if (dfs(tx, ty)) {
        return true;
    }
}

---

最后，如果这个点的相邻点都无法到达终点，那么这个点肯定也无法到达终点。

在dfs函数的最后写下

return false;

思考：这个return false的含义是不是搜索已经结束了呢？

3 4
S**.
....
.**T

尝试改变起点、终点的位置或者是添加墙壁，看看结果会有什么不同吗？