http://acm.hdu.edu.cn/showproblem.php?pid=1010
题意很好理解，不是最短路，而是dfs，虽然地图不算大，稍微注意一点的dfs也能险过，但是700+ms和78ms一对比还是让人难受
对dfs的剪枝处理，实际上就是一个逻辑推理
面对整个地图我可以做出以下判断如果 n * m - wall <= t那就一定say NO
n * m 是整个地图的大小，wall是地图中墙的个数相减之后就是最多可以走的步数，之所以取到等号是因为在第0秒的时候，已经走了一个地方了（起点）
这就是路径剪枝
接下来看一看奇偶剪枝：
奇偶剪枝:
把矩阵标记成如下形式
0,1,0,1,0
1,0,1,0,1
0,1,0,1,0
1,0,1,0,1
起点和终点奇偶不同——要走奇数步，奇偶相同——要走偶数步，与路径剪纸不同的是奇偶剪纸可以放到dfs里，对dfs的优化效果也很好
进而可以推出下面的关系（他们之间的关系有一个就是奇数-奇数=偶数，偶数-偶数=偶数，所以如果temp是奇数，那么就say no）
令 temp = (t - step) - (abs(sx - ex) + abs(sy - ey));
abs(sx - ex) + abs(sy - ey)到达终点最少还要的步数
t - step 还剩下的步数
1——》temp < 0 肯定到不了了return
2——》temp > 0
（1）temp是奇数 --》绕道多走必然多走偶数步-出去一步，进来以不，
//例如走a b你可以试一试无论怎么走再回到正轨上肯定多走偶数步所以retur
（2）temp是偶数--》可以正常dfs
#include <iostream>
#include <cstdio>
#include <string>
#include <string.h>
using namespace std;
const int maxn = 10;
int mp[10][10];
int vis[10][10];
int foot[4][2] = {1,0,-1,0,0,1,0,-1};
int n,m,t,sx,sy,ex,ey,wall;
int retflag;
void init()
{
memset(mp,0,sizeof(mp));
memset(vis,0,sizeof(vis));
retflag = 0;
wall = 0;
}
void dfs(int x,int y,int step)
{
if(x == ex && y == ey)
{
if(step == t)
{
retflag = 1;
}
return;
}
if(retflag)return;
int temp = (t - step) - (abs(sx - ex) + abs(sy - ey));
if(temp < 0 || temp & 1)
{
return;
}
for(int i = 0;i < 4;i++)
{
int nx = x + foot[i][0];
int ny = y + foot[i][1];
if(nx >= 0 && nx < n && ny >= 0 && ny < m && !vis[nx][ny] && mp[nx][ny] != 1)
{
vis[nx][ny] = 1;
dfs(nx,ny,step + 1);
vis[nx][ny] = 0;
}
}
} int main()
{
char ch;
while(~scanf("%d%d%d",&n,&m,&t))
{
getchar();
if(!n && !m && !t)break;
init();
for(int i = 0;i < n;i++)
{
for(int j = 0;j < m;j++)
{
scanf("%c",&ch);
if(ch=='X'){mp[i][j] = 1;wall++;}
if(ch=='S')
{
sx = i;
sy = j;
vis[i][j] = 1;
}
if(ch=='D')
{
ex = i;
ey = j;
}
if(ch=='.')mp[i][j] = 0;
}
getchar();
}
if(n * m - wall <= t)
{
printf("NO\n");
continue;
}
dfs(sx,sy,0);
if(retflag)printf("YES\n");
else printf("NO\n");
}
return 0;
}