背景：熟悉dfs，第一次遇见了剪枝，各种剪枝。
１.奇偶剪枝：开始一直超时，用了奇偶剪枝之后瞬间优化到312MS。
对于一个没有障碍的图，起点：s（ｘ１，ｙ１）到终点：ｅ（ｘ２，ｙ２）的理想最短路径是：ｄ＝ａｂｓ（ｘ１－ｘ２）＋ａｂｓ（ｙ１－ｙ２）．而如果中间有障 碍物的话，路径是在理想最短路径上加上一个偶数（可以证明）。这样可以看来，任何路径和理想最短路径是同奇偶的。这样就可以剪去那些不同奇偶的数据了。
２.路劲剪枝：由312MS优化到62MS，可见测试数据有多少是无用数据啊，大概是随机生成的？
如果地图中所有点走完了，能到达的最大步数，都小于时间ｔ的话肯定不行。
3.极端剪枝：结果仍然是62MS，没什么用。
用bfs求出，起点到终点的最短路径，如果最短路径都大于t的话，肯定不行。
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<queue>
using namespace std;
char map[9][9],map1[9][9];
int n,m,ans,count,ok,direction[4][2]={-1,0,0,-1,0,1,1,0},waycut;
struct place{int x,y;}start,end1,temp,temp1;
void dps(int x,int y){
if(ok != 0) return;
if(count > ans){count--;return;}
if(map[x][y] == 'D'){
if(count == ans) ok=1;
count--;
return;
}else{
map[x][y]='X';
for(int i=0;i < 4;i++){
if(map[x+direction[i][0]][y+direction[i][1]] != 'X'){
count++;
dps(x+direction[i][0],y+direction[i][1]);
}
}
map[x][y]='.';
count--;
}
}
int main(void){
while(scanf("%d%d%d",&n,&m,&ans),n*n+m*m+ans*ans){
getchar();
waycut=count=ok=0;
memset(map,'X',sizeof(map));
memset(map,'X',sizeof(map));
for(int i=1;i <= n;i++){
for(int j=1;j <= m;j++){
scanf("%c",&map[i][j]);
if(map[i][j] == 'S'){
start.x=i;
start.y=j;
map[i][j]='X';
}else if(map[i][j] == 'D'){
end1.x=i;
end1.y=j;
waycut++;
}else if(map[i][j] == '.') waycut++; //count the numbers of '.' .
map1[i][j]=map[i][j];
}
getchar();
}
//bfs find the shortest steps.
queue<struct place> q;
q.push(start);
int q_size=1,steps=0;
while(1){
bool over=false;
steps++;
for(int i=0;i < q_size;i++){
temp=q.front();
q.pop();
map1[temp.x][temp.y]='X';
for(int j=0;j < 4;j++){
temp1.x=temp.x+direction[j][0];
temp1.y=temp.y+direction[j][1];
if(temp1.x == end1.x && temp1.y == end1.y) over=true;
if(map1[temp1.x][temp1.y] == '.') q.push(temp1);
}
}
q_size=q.size();
if(over || !q_size ) break;
}
if(steps > ans) ok=2;
if(waycut < ans) ok=2;
int min_distance=abs(end1.x-start.x)+abs(end1.y-start.y); //奇偶剪枝。
if(min_distance % 2 != ans%2) ok=2;
dps(start.x,start.y);
if(ok == 1) printf("YES\n");
else printf("NO\n");
}
return 0;
}