HDU1010-Tempter of the Bone 题解

题目链接 昨晚就在写这道题，写了一个小时还是TLE。今天早上起床之后再看，发现是没有对flag==true的情况进行剪枝（属于是对递归的理解不够深刻了）。

#include <bits/stdc++.h>
using namespace std;
int n,m,t,dx,dy,gox[4]={1,0,-1,0},goy[4]={0,1,0,-1};
char mp[10][10];
bool vis[10][10];
bool flag=false;
void dfs(int nx,int ny,int nt){
    if(nt>t||flag||nt+abs(dx-nx)+abs(dy-ny)>t) return ; //flag==true要结束，是为了避免上面层级继续搜索下去
    if(mp[nx][ny]=='D'&&nt==t){
        flag=true;
        return ;//这里只是最后一层结束了，但上面层级的搜索可能还在进行
    }
    for(int i=0;i<4;++i){
        int tx=nx+gox[i],ty=ny+goy[i];
        if(vis[tx][ty]||mp[tx][ty]=='X'||tx<0||ty<0||tx>=n||ty>=m) continue;
        vis[tx][ty]=true;
        dfs(tx,ty,nt+1);
        vis[tx][ty]=false;
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
	while(cin>>n>>m>>t){
        int sx,sy;
        if(n==0&&m==0&&t==0) break;
        memset(vis,0,sizeof(vis));
        for(int i=0;i<n;++i){
            for(int j=0;j<m;++j){
                cin>>mp[i][j];
                if(mp[i][j]=='S') sx=i,sy=j,vis[i][j]=true;
                else if(mp[i][j]=='D') dx=i,dy=j;
            }
        }
        int dis=abs(dx-sx)+abs(dy-sy);
        if(dis>t||((dis%2)!=(t%2))){
            cout<<"NO\n";//如果直接从起点走到终点（曼哈顿距离）都超时，那肯定不行
            continue ;//奇偶剪枝，两点之间任何路径的步数的奇偶性相同，即与曼哈顿距离的奇偶性相同。不同一定无解。
        }
        flag=false;
        dfs(sx,sy,0);
        cout << (flag ? "YES\n" : "NO\n");
    }
	return 0;
}