深度优先搜索算法-dfs解析

迷宫问题

有一个迷宫：

    S**.
    ....
    ***T

（其中字符S表示起点，字符T表示终点，字符*表示墙壁，字符.表示平地。你需要从起点S出发前往终点T，在每一步中你只能向上下左右相邻的位置移动一次，并且不能走出地图范围或穿过墙壁；每个位置只能被访问一次）

现在需要你求出是否可以走出这个迷宫

我们将这个走迷宫过程称为dfs（深度优先搜索）算法。

思路

当我们搜索到了某一个点，有这样3种情况：

1.当前我们所在的格子就是终点。

如果不是终点，则遍历上下左右四个方向，并依次检查相邻的四个点是否为合法的目标点；如果是，则移动到目标点并重复上述步骤

当然也有可能我们在探索过程中陷入了僵局（上方、下方、左方、右方这四个方向都不符合规定条件），这时我们需要采取回退策略，在上一步骤所在位置重新审视周边区域以寻找新的可行路径。

怎样才能算“合法的目标点”？

1.必须在所给定的迷宫范围内

2.不能是迷宫边界或墙。

3.该节点在整个搜索过程中未被访问过（为了避免同一节点被多次访问而导致陷入无限循环——在两个节点之间来回切换的情况，通常会对每个节点进行标记处理。）

实现代码

 #include <iostream>

    
 using namespace std;
    
 int n, m;