http://acm.hdu.edu.cn/showproblem.php?pid=1010
1 //////////////////////////////////////////////////////////////////////////////////
2 //以前寫的1010是參考別人的,今天把它寫了下(省賽題）,
3 //過程相當艱難，忘了road=0,以至于少了一個剪枝,TLE,調試了
4 //N久，沒發現，以至于去優化dfs過程，最后發現，把第一次交
5 //的改了后就過了，不過比未優化時慢了100ms左右
不過還是
6 //比較開心的，雖然囧
7 /////////////////////////////////////////////////////////////////////////////////
8 #include <iostream>
9
10 using namespace std;
11 const int N=8;
12 const int M=8;
13 char mp[N][M];
14 int dir[4][2]={1,0,-1,0,0,-1,0,1};
15 int n,m,t,road;
16 struct Node
17 {
18 int xi,yi;
19 int time;
20 Node(int x=0,int y=0,int t=0):xi(x),yi(y),time(t){};
21 }start,end;
22 int gf;
23 inline void Input()
24 {
25 road=0;
26 gf=0;
27 for(int i=0;i<n;i++){
28 for(int j=0;j<m;j++){
29 cin>>mp[i][j];
30 if(mp[i][j]=='S'){
31 start.xi=i;
32 start.yi=j;
33 mp[i][j]='X';
34 }
35 if(mp[i][j]=='D'){
36 end.xi=i;
37 end.yi=j;
38 }
39 if(mp[i][j]=='.')
40 ++road;
41 }
42 }
43 }
44 inline bool optimize(const Node& a,const Node& b,const int ti)
45 {
46 if(((a.xi+a.yi+b.xi+b.yi)&1) != (ti&1) )return false;
47 if(abs(a.xi-b.xi)+abs(a.yi-b.yi)>ti)
48 return false;
49 return true;
50 }
51 int dfs(Node const& c,int ti)
52 {
53 if(gf)return 1;
54 Node ans;
55 --ti;
56 for(int i=0;i<4;i++){
57 ans.xi=c.xi+dir[i][0];
58 ans.yi=c.yi+dir[i][1];
59 ans.time=c.time+1;
60 if(ans.time>t)continue;
61 if(ans.xi==end.xi && ans.yi==end.yi && ans.time == t){
62 gf=1;
63 return 1;
64 }
65 if(mp[ans.xi][ans.yi]=='D')continue;
66 if(ans.xi<0||ans.yi<0||ans.xi>=n||ans.yi>=m)
67 continue;
68 if(mp[ans.xi][ans.yi]=='X')
69 continue;
70 mp[ans.xi][ans.yi]='X';
71 if(optimize(ans,end,ti))
72 dfs(ans,ti);
73 if(gf)return 1;
74 mp[ans.xi][ans.yi]='.';
75 }
76 return 0;
77 }
78 int main()
79 {
80 while(cin>>n>>m>>t,n+m+t){
81 Input();
82 if(road+1<t){
83 cout<<"NO\n";
84 }
85 else if(optimize(start,end,t)){
86 if(dfs(start,t))
87 cout<<"YES\n";
88 else cout<<"NO\n";
89 }
90 else cout<<"NO\n";
91 }
92 return 0;
93 }
posted on 2008-07-21 15:59
小果子 閱讀(1158)
評論(0) 編輯 收藏 引用