HDOJ1010深搜+数学奇偶性剪枝

/*
	1010标准搜索题，不过一开始很容易把题目看错
	易错的理解：广搜，在t秒之内从起点走到终点即可。纯模版题
	正确的理解：深搜，每个点在只能去一次的情况下，而且不能停留只能经过
			    这就要求我们把所有的路径遍历
	方法：深搜+数学奇偶性剪枝
	效率：578ms 
*/

#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <math.h>
#include <vector>
#include <string>
#include <cstring>
#include <sstream>
using namespace std;

#define input freopen("input.txt","r",stdin)
#define output freopen("output.txt","r",stdout)
#define For1(i,a,b) for (i=a;i<b;i++)
#define For2(i,a,b) for (i=a;i<=b;i++)
#define Dec(i,a,b) for (i=a;i>b;i--)
#define Dec2(i,a,b) for (i=a;i>=b;i--)
#define Sca(x) scanf("%d",&x)
#define Fill(x,a) memset(x,a,sizeof(x))
#define MAXN 0x7fffffff

int dir_x[]={0,1,-1,0,0};//x方向常量 
int dir_y[]={0,0,0,1,-1};//y方向常量 
int map[10][10];//存储地图，将题中的字母全部改为习惯的0断1通 
bool book[10][10];//深搜模版中标记每个点是否走过 
int n,m,t,i,j,k;
int sx,sy,ex,ey;//sx==startx,sy==starty,ex==endx,ey==endy
char in[10];
int flag;//标记是否有解 

void dfs(int cur_x,int cur_y,int steps)//传入的是当前在哪个坐标（x，y），已经从起点走了多少步 
{
	if (steps>t) return;//不可能有解则返回 
	if (cur_x==ex&&cur_y==ey&&steps==t)//满足条件为有解 
	{
		flag=1;return;
	}
	int i,j,k,newx,newy;
	for(k=1;k<=4;k++)//四种方向 
	{
		newx=cur_x+dir_x[k];
		newy=cur_y+dir_y[k];
		if (newx>0&&newx<=n&&newy>0&&newy<=m&&!book[newx][newy]&&!map[newx][newy])
		//坐标在矩形内，坐标没有访问过，坐标可以访问（此点不为墙） 
		{
			book[newx][newy]=1;//标记已走过 
			dfs(newx,newy,steps+1);
			if (flag) return;//如果有解即使返回，不需要继续搜索 
			book[newx][newy]=0;//取消标记 
		}
	}
	return;
}

int main() 
{
	//input;
	while(cin>>n>>m>>t)
	{
		Fill(map,0);
		Fill(book,0);
		if (!n&&!m&&!t) break;
		For2(i,1,n)
		{
			cin>>in;
			For2(j,1,m)
				if (in[j-1]=='S')
					map[i][j]=0,sx=i,sy=j;
				else if (in[j-1]=='D')
					map[i][j]=0,ex=i,ey=j;
				else if (in[j-1]=='X')
					map[i][j]=1;
		}//如何处理字符
		if (sx==ex&&sy==ey)//剪枝一，如果终点和起点在一起（其实不可能） 
		{
			cout<<"YES"<<endl;
			continue;
		}
		if ((abs(sx-ex)+abs(sy-ey)>t)||((t-abs(sx-ex)-abs(sy-ey))%2==1))
		//剪枝2，若起点与终点的坐标轴距离大于t，或者之差为奇数则不可能走得到 
		{
			cout<<"NO"<<endl;
			continue;
		}
		book[sx][sy]=1;
		flag=0;
		dfs(sx,sy,0);
		if (flag)
			cout<<"YES"<<endl;
		else
			cout<<"NO"<<endl;
	}
	return 0;
}