杭电1010

梦里梦外; 2022-06-04 00:45 167阅读 0赞

**杭电1010**

**1.奇偶性剪枝**

**可以把map看成这样：**

**0 1 0 1 0 1**

**1 0 1 0 1 0**

**0 1 0 1 0 1**

**1 0 1 0 1 0**

**0 1 0 1 0 1**

**从为 0 的格子走一步，必然走向为 1 的格子**

**从为 1 的格子走一步，必然走向为 0 的格子**

**即：0 ->1或1->0 必然是奇数步 0->0 走1->1 必然是偶数步**

**所以当遇到从0走向0但是要求时间是奇数的，或者，从1走向0但是要求时间是偶数的都可以直接判断不可达！**

**\[cpp\]** [view plain][] [copy][view plain]

1.  \#include <iostream.h> 
2.  \#include <string.h> 
3.  \#include <stdlib.h> 
4.  **char** map\[9\]\[9\]; 
5.  **int** n,m,t,di,dj; 
6.  **bool** escape; 
7.  **int** dir\[4\]\[2\]=\{ \{0,-1\},\{0,1\},\{1,0\},\{-1,0\}\}; 
8.  **void** dfs(**int** si,**int** sj,**int** cnt) 
9.  \{ 
10. **int** i,temp; 
11. **if**(si>n||sj>m||si<=0||sj<=0) 
12. **return**; 
13. **if**(cnt==t&&si==di&&sj==dj) 
14.  escape=1; 
15. **if**(escape) 
16. **return**; 
17.  temp=(t-cnt)-abs(si-di)-abs(sj-dj); 
18. **if**(temp<0||temp&1) 
19. **return**; 
20. **for**(i=0;i<4;i++) 
21.  \{ 
22. **if**(map\[si+dir\[i\]\[0\]\]\[sj+dir\[i\]\[1\]\]!='X') 
23.  \{ 
24.  map\[si+dir\[i\]\[0\]\]\[sj+dir\[i\]\[1\]\]='X'; 
25.  dfs(si+dir\[i\]\[0\],sj+dir\[i\]\[1\],cnt+1); 
26.  map\[si+dir\[i\]\[0\]\]\[sj+dir\[i\]\[1\]\]='.'; 
27.  \} 
28.  \} 
29. **return**; 
30. \} 
31. **int** main() 
32. \{ 
33. **int** i,j,si,sj; 
34. **while**(cin>>n>>m>>t) 
35.  \{ 
36. **if**(n==0&&m==0&&t==0) 
37. **break**; 
38. **int** wall=0; 
39. **for**(i=1;i<=n;i++) 
40. **for**(j=1;j<=m;j++) 
41.  \{ 
42.  cin>>map\[i\]\[j\]; 
43. **if**(map\[i\]\[j\]=='S') 
44.  \{ 
45.  si=i; 
46.  sj=j; 
47.  \} 
48. **else****if**(map\[i\]\[j\]=='D') 
49.  \{ 
50.  di=i; 
51.  dj=j; 
52.  \} 
53. **else****if**(map\[i\]\[j\]=='X') 
54.  wall++; 
55.  \} 
56. **if**(n\*m-wall<=t) 
57.  \{ 
58.  cout<<"NO"<<endl; 
59. **continue**; 
60.  \} 
61.  escape=0; 
62.  map\[si\]\[sj\]='X'; 
63.  dfs(si,sj,0); 
64. **if**(escape) 
65.  cout<<"YES"<<endl; 
66. **else**
67.  cout<<"NO"<<endl; 
68.  \} 
69. **return** 0; 
70. \} 
71.

[view plain]: http://blog.csdn.net/acdreamers/article/details/7802036#