需要剪枝否则会超时，然后就是基本的深搜了
#include<cstdio>
#include<stdio.h>
#include<cstdlib>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
#define INF 0x3f3f3f3f
#define MAX 1005 using namespace std; char Map[MAX][MAX]; int time,n,m,sx,sy,ex,ey,v[][]={{,},{,},{-,},{,-}},ok; bool check(int x,int y)
{
if(x>= && x<n && y>= && y<m && Map[x][y]!='X')
return true;
return false;
} void DFS(int x,int y,int step)
{
if(x==ex && y==ey && step==time)
{
ok=;
return;
}
else if(step >= time || ok)
return;
for(int i=;i<;i++)
{
int new_x=x+v[i][];
int new_y=y+v[i][];
if(check(new_x,new_y))
{
Map[new_x][new_y]='X';
DFS(new_x,new_y,step+);
Map[new_x][new_y]='.';
}
}
} int main()
{
while(scanf("%d%d%d",&n,&m,&time),n+m+time)
{
ok=;
for(int i=;i<n;i++)
scanf("%s",Map[i]);
for(int i=;i<n;i++)
{
for(int j=;j<m;j++)
{
if(Map[i][j]=='S')
{
sx=i;
sy=j;
}
if(Map[i][j]=='D')
{
ex=i;
ey=j;
}
}
}
int k1=abs(sx-ex);
int k2=abs(sy-ey);
if((time-(k1+k2))%)//奇偶剪纸
{
printf("NO\n");
continue;
}
if(sx==ex && sy==ey)
{
printf("YES\n");
continue;
}
Map[sx][sy]='X';
DFS(sx,sy,);
if(ok)
printf("YES\n");
else
printf("NO\n");
}
return ;
}