题目原文：http://acm.hdu.edu.cn/showproblem.php?pid=1010
题目大意：给出起始位置和终点位置，要求在指定的时间刚好到达终点时间，每移动一步一秒，并且不能返回。
题目分析：
1。起初以为能用BFS做，后来发现，必须在指定的时间内抵达终点才行，BFS无法达到要求。
2。要求在指定时间内到达，唯一想法就是能不能枚举出所有抵达方案，再在通过检查时间时间是否吻合，得到结果，这就自然想到了用DFS进行搜索。
3。DFS搜索完成后，提交发现超时，看样子还得剪枝才行，无奈啊，百度一下。
4。剪枝方法：奇偶剪枝
把map看作
0 1 0 1 0 1
1 0 1 0 1 0
0 1 0 1 0 1
1 0 1 0 1 0
0 1 0 1 0 1
从 0->1 需要奇数步
从 0->0 需要偶数步
那么设所在位置 (x,y) 与 目标位置 (dx,dy)
如果abs(x-y)+abs(dx-dy)为偶数，则说明 abs(x-y) 和 abs(dx-dy)的奇偶性相同，需要走偶数步
如果abs(x-y)+abs(dx-dy)为奇数，那么说明 abs(x-y) 和 abs(dx-dy)的奇偶性不同，需要走奇数步
理解为 abs(si-sj)+abs(di-dj) 的奇偶性就确定了所需要的步数的奇偶性！！
而 (ti-setp)表示剩下还需要走的步数，由于题目要求要在 ti时 恰好到达，那么 (ti-step) 与 abs(x-y)+abs(dx-dy) 的奇偶性必须相同
因此 temp=ti-step-abs(dx-x)-abs(dy-y) 必然为偶数！
5。最后一点：整个图的可以移动步数应该大于指定的时间
#include "iostream"
#include <math.h>
using namespace std;
int dir[4][2]={{-1,0},{0,1},{1,0},{0,-1}};
int n,m;
char a[7][7];
int sx,sy,dx,dy;
int ti,flag;
void DfsSerch(int x,int y,int step)
{
/////////////////////////////////////
int temp;
temp=ti-step-abs(dx-x)-abs(dy-y);
if (temp<0||temp%2==1) return;
////////////////////////////////////
int tx,ty;
for(int i=0;i<4;i++) //方向探索
{
tx=x+dir[i][0];
ty=y+dir[i][1];
if (a[tx][ty]=='D'&&step==ti-1)
{
flag=1;
return ;
}
if(a[tx][ty]=='.'&&(tx>=0&&tx<n)
&&(ty>=0&&ty<m))
{
a[tx][ty]='X'; //标记访问
DfsSerch(tx,ty,step+1);
a[tx][ty]='.'; //回溯取消标记
if(flag==1) return;//找到直接返回
}
}
}
int main()
{
while (cin>>n>>m>>ti&&n!=0||m!=0||ti!=0)
{
///////////////////////////////////////
//输入数据
int wall=0;
for (int i=0;i<n;i++)
for(int j=0;j<m;j++)
{
cin>>a[i][j];
if(a[i][j]=='S')
{
sx=i;
sy=j;
}
if (a[i][j]=='D')
{
dx=i;
dy=j;
}
if (a[i][j]=='X')
{
wall++;
}
}//for-for
/////////////////////////////////////
flag=0;
if (n*m-wall<=ti)
{
cout<<"NO"<<endl;
continue;
}
DfsSerch(sx,sy,0);
if(flag==1)
cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
return 0;
}