#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
const int maxn=10;
bool vis[maxn][maxn];
char mapp[maxn][maxn];
bool flag;
int tem;
int n,m,t,di,dj,wall,si,sj;
int step[4][2]= {{0,1},{0,-1},{1,0},{-1,0}};
void dfs(int sx,int sy,int stepp)
{
if(flag)
return;
if(sx==di&&sy==dj&&stepp==t)
{
flag=1;
return;
}
tem=t-stepp-(abs(di-sx)+abs(dj-sy));
//前半部分是剩余可用时间,后半部分是最短步数
if(tem<0||tem&1)
return;
//如果可用时间小于最短步数,或者tem为奇数
//进行剪枝
int dx,dy;
for(int i=0; i<4; ++i)
{
dx=sx+step[i][0];
dy=sy+step[i][1];
if(dx<0||dx>=n||dy<0||dy>=m)
continue;
if(mapp[dx][dy]!='X'&&!vis[dx][dy])
{
vis[dx][dy]=1;
dfs(dx,dy,stepp+1);
if(flag)
return;
vis[dx][dy]=0;
}
}
return;
}
int main()
{
while(~scanf("%d%d%d",&n,&m,&t))
{
if(!n)
break;
memset(vis,0,sizeof(vis));
wall=0;
flag=0;
for(int i=0; i<n; ++i)
scanf("%s",&mapp[i]);
for(int i=0; i<n; ++i)
for(int j=0; j<m; ++j)
{
if(mapp[i][j]=='X')
{
wall++;
}
else if(mapp[i][j]=='D')
{
di=i;
dj=j;
}
else if(mapp[i][j]=='S')
{
si=i;
sj=j;
}
}
if(t>n*m-wall+1)//时间大于可用格子数
{
//剪枝
printf("NO\n");
continue;
}
vis[si][sj]=1;
dfs(si,sj,0);
if(flag)
printf("YES\n");
else
printf("NO\n");
}
return 0;
}
1.奇数偶数剪枝的知识点参考大佬的博客：https://blog.csdn.net/yinghui_yht/article/details/52971849
2.利用深搜有利于遍历所有情况（自己用的BFS还没做出来）
