题意是问从S出发，终点为D，如果能刚好k步到达终点就输出YES，否则输出NO。如果直接深搜会超时，所以这里需要进行奇偶剪枝。
奇偶剪枝就是比如说不考虑障碍物的情况下起点为S_x,S_y，终点为E_x,E_y，那么起点到终点的最短距离为dist=|S_x-E_x| |S_y-E_y|，当dist和题目中所需要的走的步数k同奇同偶的时候是可以走到的，否则是一定走不到的。所以这道题就是判断k 和 已经走过的步数 当前点到终点的最短距离的奇偶性是否相同。
AC代码：
代码语言：javascript复制#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
const int MAXN = 105;
char MAP[MAXN][MAXN];
int vis[MAXN][MAXN];
int dir[4][2] = {1,0,0,1,-1,0,0,-1};
int n,m,k,flag,S_x,S_y,E_x,E_y;
int dist(int x1,int y1,int x2,int y2){ // 计算当前点到终点的最短距离
return (abs(x1-x2) abs(y1-y2));
}
void dfs(int x,int y, int step){
if(x == E_x && y == E_y && step == k){
flag = 1;
return ;
}
if(flag)return ;
for(int i=0;i<4;i ){
int X = x dir[i][0];
int Y = y dir[i][1];
if(X < 0 || Y < 0 || X >= n || Y >= m || MAP[X][Y] == 'X' || vis[X][Y]) continue;
//if((1 step dist(X,Y,E_x,E_y) <= k) &&((dist(X,Y,E_x,E_y) 1 step) % 2 == k % 2)){
vis[X][Y] = 1;
dfs(X,Y,step 1);
// if(flag)return ;
vis[X][Y] = 0;
}
//}
}
int main()
{
while(~scanf("%d%d%d",&n,&m,&k)){
if(n == 0 && m == 0 && k == 0) break;
flag = 0;
for(int i=0;i<n;i ){
scanf("%s",MAP[i]);
}
for(int i=0;i<n;i ){
for(int j=0;j<m;j ){
if(MAP[i][j] == 'S'){
S_x = i;
S_y = j;
}
if(MAP[i][j] == 'D'){
E_x = i;
E_y = j;
}
}
}
if((dist(S_x,S_y,E_x,E_y) % 2 != k % 2) || dist(S_x,S_y,E_x,E_y) > k){// 如果最短距离大于k是肯定到不了的
printf("NOn");
continue;
}
else{
memset(vis,0,sizeof(vis));
vis[S_x][S_y] = 1;
dfs(S_x,S_y,0);
if(flag)printf("YESn");
else printf("NOn");
}
}
return 0;
}
