HDU 1010 Tempter of the Bone(dfs+剪枝)

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
const int MAXN = 105;
char MAP[MAXN][MAXN];
int vis[MAXN][MAXN];
int dir[4][2] = {1,0,0,1,-1,0,0,-1};
int n,m,k,flag,S_x,S_y,E_x,E_y;

int dist(int x1,int y1,int x2,int y2){              // 计算当前点到终点的最短距离
	return (abs(x1-x2)+abs(y1-y2));
}

void dfs(int x,int y, int step){
	if(x == E_x && y == E_y && step == k){
		flag = 1;
		return ;
	}
	if(flag)return ;
	for(int i=0;i<4;i++){
		int X = x + dir[i][0];
		int Y = y + dir[i][1];
	  if(X < 0 || Y < 0 || X >= n || Y >= m || MAP[X][Y] == 'X' || vis[X][Y]) continue;
		//if((1+step+dist(X,Y,E_x,E_y) <= k) &&((dist(X,Y,E_x,E_y)+1+step) % 2 == k % 2)){
			vis[X][Y] = 1;
			dfs(X,Y,step + 1);
			// if(flag)return ;
			vis[X][Y] = 0;
		}
	//}
}

int main()
{
	while(~scanf("%d%d%d",&n,&m,&k)){
		if(n == 0 && m == 0 && k == 0) break;
		flag = 0;
		for(int i=0;i<n;i++){
			scanf("%s",MAP[i]);
		}
		for(int i=0;i<n;i++){
			for(int j=0;j<m;j++){
				if(MAP[i][j] == 'S'){
					S_x = i;
					S_y = j;
				}
				if(MAP[i][j] == 'D'){
					E_x = i;
					E_y = j;
				}
			}
		}
		if((dist(S_x,S_y,E_x,E_y) % 2 != k % 2) || dist(S_x,S_y,E_x,E_y) > k){// 如果最短距离大于k是肯定到不了的
			printf("NO\n");
			continue;
		}
		else{
			memset(vis,0,sizeof(vis));
			vis[S_x][S_y] = 1;
			dfs(S_x,S_y,0);
			if(flag)printf("YES\n");
			else printf("NO\n");
		}
	}
	return 0;
}