题目大意：给定你起点S，和终点D，问你是否能在 T 时刻恰好到达终点D。
题解：首先很容易将题目误解为T时刻之前到达，那么广搜无疑，但是要在T时刻刚好到达，就只能DFS了，以下是两个剪枝：
1.地图方格数减去障碍数再减1小于T，则直接无解：因为无法在T时刻到达；
2.奇偶剪枝：每一步走后，曼哈顿距离与所走步数之和与T的差值必定是偶数，否则剪枝。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75 |
#include<iostream>#include<cmath>#include<cstring>using
namespace std;int n,m,t,ex,ey;bool
V[10][10],flag,ans;char
map[10][10];void
DFS(int
i,int j,int step){ if(flag) return
; if(step>t) return
; if(i<0||i>=n||j<0||j>=m) {return
;} if(map[i][j]==‘D‘&&step==t) {flag=ans=true; return
;} int
temp=abs(i-ex)+abs(j-ey); temp=t-temp-step; if(temp&1) return
; if(!V[i-1][j]&&map[i-1][j]!=‘X‘) { V[i-1][j]=true; DFS(i-1,j,step+1); V[i-1][j]=false; } if(!V[i+1][j]&&map[i+1][j]!=‘X‘) { V[i+1][j]=true; DFS(i+1,j,step+1); V[i+1][j]=false; } if(!V[i][j-1]&&map[i][j-1]!=‘X‘) { V[i][j-1]=true; DFS(i,j-1,step+1); V[i][j-1]=false; } if(!V[i][j+1]&&map[i][j+1]!=‘X‘) { V[i][j+1]=true; DFS(i,j+1,step+1); V[i][j+1]=false; }}int
main(){ int
i,j,x,y,k; while(cin>>m>>n>>t&&(m||n||t)) { memset(V,false,sizeof(V)); k=0; for(i=0;i<n;i++) { for(j=0;j<m;j++) { cin>>map[i][j]; if(map[i][j]==‘S‘) { x=i;y=j; V[i][j]=true; } if(map[i][j]==‘D‘) { ex=i;ey=j; } if(map[i][j]==‘X‘)k++; } } ans=flag=false; if(n*m-k-1>=t) DFS(x,y,0); if(ans) cout<<"YES"<<endl; else
cout<<"NO"<<endl; } return
0;} |
原文：http://www.cnblogs.com/forever97/p/3542271.html