ZOJ 2110 Tempter of the Bone DFS搜索+奇偶剪枝

二维网格中的两个点a,b。设其最短距离为d（网格只能走横竖线，不能走斜线），那么实际从a到b的路程可能比d大或者相等，但与d的差一定是偶数，这就是我理解的奇偶剪枝的原理

#include<stdio.h>
#include<queue>
#include<string.h>
#include<stdlib.h>
#include<math.h>
using namespace std;
int m,n,t;
char map[10][10];
bool visit[10][10];
int sx,sy,ex,ey;
int h[4]={1,-1,0,0};
int g[4]={0,0,1,-1};

int dfs(int xx,int yy,int time){
    int i;
    if(xx==ex && yy==ey && time==t)
		return 1;
    
    for(i=0;i<4;i++){
		int x=xx+h[i];
		int y=yy+g[i];

		if(x>=m || x<0 || y>=n ||y<0)
			continue;
		if(map[x][y]=='X')
			continue;

		int temp=(t-(time+1))-(int)(abs(x-ex)+abs(y-ey));
        if(temp<0 || temp%2==1)
			continue;
		map[x][y]='X';
		if(dfs(x,y,time+1))
			return 1;
		map[x][y]='.';
	}
	return 0;
}
int main(){
    int i,j,k;
    while(scanf("%d %d %d",&m,&n,&t) && !(m==0 && n==0 && t==0)){
		int sum=0;
		for(i=0;i<m;i++){
			scanf("%s",map[i]);                 
		}                
		for(i=0;i<m;i++)
			for(j=0;j<n;j++){
				if(map[i][j]=='S'){
					sx=i;
					sy=j;  
				}     
				if(map[i][j]=='D'){
					ex=i;
					ey=j;  
				} 
				if(map[i][j]=='.')
					sum++;
			}

        if(sum+1<t){
			printf("NO\n");
			continue;
		}
                    
        map[sx][sy]='X';
        if(dfs(sx,sy,0))
			printf("YES\n");
	else
			printf("NO\n");                 
    }
}