http://acm.hdu.edu.cn/showproblem.php?pid=1010
用到了奇偶剪枝：
0 1 0 1
1 0 1 0 如图，设起点为s，终点为e，s->e的最短步数为t. sum=t+extra. [因为extra无论怎么走，最终都要返回其中一条最短路径上，即有来回，所以extra=2*某个数，一定是偶数。
0 1 0 1
1 0 1 0
【所以此题中，v-step表示还可以走多少步，abs(x-x2)+abs(y-y2)为此刻点到终点位置，由上面剪枝分析，两者之差一定为偶数。所以根据小学数学，奇-奇=偶，偶-偶=偶，可知两数奇偶性相同（有用吗）】
#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define mem(a) memset(a,0,sizeof(a))
#define ll long long
int fa[][]={{,},{,-},{,},{-,}};
int n,m,v;
char mo[][];
int mark[][];
int ans,x1,x2,y3,y2;
int coun;
int abs(int a)
{
if (a<) return -a;
return a;
}
void dfs(int x,int y,int step)
{
if(ans) return ;
if(x==x2&&y==y2&&step==v) {ans=;return ;}
int v1=v-step-(abs(x-x2)+abs(y-y2));
if(v1<||v1&)
return ;
for(int i=;i<;i++)
{
int xx=x+fa[i][];
int yy=y+fa[i][];
if(xx>=&&xx<n&&yy>=&&yy<m&&mark[xx][yy]==&&mo[xx][yy]!='X')
{
mark[xx][yy]=;
dfs(xx,yy,step+);
if(ans) return ;
mark[xx][yy]=;
}
}
return ;
}
int main()
{
while(~scanf("%d%d%d",&n,&m,&v)&&(n||m||v))
{
ans=coun=;
mem(mark);
for(int i=;i<n;i++)
scanf("%s",mo[i]);
for(int i=;i<n;i++)
{
for(int j=;j<m;j++)
{
if(mo[i][j]=='S')
{x1=i;y3=j;}
if(mo[i][j]=='D')
{x2=i;y2=j;}
if(mo[i][j]=='X')
coun++;
}
}
if(v>n*m-coun-)
{
printf("NO\n");
continue;
}
mark[x1][y3]=;
dfs(x1,y3,);
if(ans==)printf("YES\n");
else printf("NO\n");
}
return ;
}