题目链接：点击进入
思路
（1）首先：可以先判断空白格数量（不算开头结尾）与时间的关系； 如果可以实现要求，那么：
空白格数量 + 1 >= 时间（即为 n * m - sum - 1 >= t （n * m - sum - 2 + 1 >= t））（sum为障碍的数目）
（2）其次：用 dfs + 剪枝（奇偶剪枝）判断答案。 奇偶剪枝：起点为 ( sx , sy ) ，终点为（ex , ey），给定 t 步恰好走到终点，若 t - [ abs ( ex - sx ) + abs ( ey - sy ) ] 结果为非偶数（奇数），则 无法 在 t 步恰好到达； 在搜索里应用为：总步数-已走步数-（此点跟终点的曼哈顿距离（abs ( x - ex ) + abs ( y - ey ) ））应当大于零同时为偶数
代码
#include<cstdio>
#include<cstring>
#include<string>
#include<iostream>
#include<algorithm>
#include<queue>
#define INF 0x3f3f3f3f
using namespace std
;
const int d
[4][2]={1,0,-1,0,0,1,0,-1};
char mp
[110][110];
bool vis
[110][110];
int n
,m
,t
,ex
,ey
,fx
,fy
,flag
;
void dfs(int x
,int y
,int step
)
{
if(x
==ex
&&y
==ey
&&step
==t
) flag
=1;
if(flag
) return ;
int tmp
=t
-step
-abs(ex
-x
)-abs(ey
-y
);
if(tmp
<0||tmp
&1) return ;
for(int i
=0;i
<4;i
++)
{
int xx
=x
+d
[i
][0];
int yy
=y
+d
[i
][1];
if(xx
<=0||yy
<=0||xx
>n
||yy
>m
) continue;
if(vis
[xx
][yy
]||mp
[xx
][yy
]=='X') continue;
vis
[xx
][yy
]=1;
dfs(xx
,yy
,step
+1);
vis
[xx
][yy
]=0;
}
}
int main()
{
while(~scanf("%d%d%d",&n
,&m
,&t
))
{
if(!n
&&!m
&&!t
) break;
int sum
=0;
for(int i
=1;i
<=n
;i
++)
{
scanf("%s",mp
[i
]+1);
}
for(int i
=1;i
<=n
;i
++)
{
for(int j
=1;j
<=m
;j
++)
{
if(mp
[i
][j
]=='S') fx
=i
,fy
=j
;
if(mp
[i
][j
]=='D') ex
=i
,ey
=j
;
if(mp
[i
][j
]=='X') sum
++;
}
}
if(n
*m
-sum
-1<t
) printf("NO\n");
else
{
flag
=0;
memset(vis
,0,sizeof(vis
));
vis
[fx
][fy
]=1;dfs(fx
,fy
,0);
if(flag
) printf("YES\n");
else printf("NO\n");
}
}
return 0;
}
