深度优先搜索最优性剪枝

对于求最优解的一类问题，通常可以用可行性剪枝，比如再求解迷宫最短路的时候，如果发现当前的步数已经超过了当前的最优解，那么当前状态开始的搜索都是多余的，因为这样搜索下去永远都不可能搜到更优解。通过这样的剪枝，可以省去大量多余的计算。
此外，在搜索是否有可行解的过程中，一旦找到了一组可行解，后面的搜索都不必再进行了，这算是最优性剪枝的一个特例。

有一个 n×m 大小的迷宫。其中字符’S’表示起点，字符’T’表示终点，字符’*‘表示墙壁，字符’.‘表示平地。你需要从’S’出发走到’T’，每次只能向上下左右相邻的位置移动，并且不能走出地图，也不能走进墙壁。保证迷宫至少存在一种可行的路径，输出’S’走到’T’的最少步数。

这道题我们通常会用BFS解决这个问题，搜索到的第一个结果就是答案。现在我们考虑用DFS来解决这个问题，第一个搜到的答案ans不一定就是正解，但是正解一定小于等于ans。于是，如果当然步数大于等于ans就直接剪枝，并且每找到一个可行的答案，都会更新ans。

首先定义一些全局变量，n、m为迷宫的行数和列数，maze记录迷宫各个位置是否可以走，vis记录DFS过程中当前位置是否被访问过，dir表示每次枚举的四个方向，ans记录当前到达重点的最小步数，初始值为一个在题目中相当于无限大的数。
in函数用于判断每次扩展的位置是否在迷宫中。
dfs一共有3个参数，x、y表示当前位置的坐标，step表示当前的步数。分别在函数的入口处和出口处更新当前位置是否访问，然后枚举四个方向，如果(tx,ty)满足在边界内、不是墙、没有访问过，就继续扩展，并且步数增加1。
如果当前步数大于等于ans就剪枝，因为继续搜下去不可能更优了。如果当前位置为终点，就更新ans并返回。

示例代码：

#include 
#include 
#include 
using namespace std;
int n,m;
string maze[110];
bool vis[110][110];
int dir[4][2]={{-1,0},{0,-1},{1,0},{0,1}};
int ans=100000;
bool in(int x,int y){
    return 0<=x && x<n && 0<=y && y<m;
}
void dfs(int x,int y,int step){
    if(step>=ans){
        return;
    }
    if(maze[x][y]=='T'){
        ans=step;
        return;
    }
    vis[x][y]=1;
    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]){
            dfs(tx,ty,step+1);
        }
    }
    vis[x][y]=0;
}
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;
            }
        }
    }
    dfs(x,y,0);
    cout<<ans<<endl;
    return 0;
}