POJ3009-Curling 2.0
轉(zhuǎn)載請(qǐng)注明出處：優(yōu)YoU http://user.qzone.qq.com/289065406/blog/1303548481
?
大致題意：
哈哈，玩過(guò)“GBA口袋怪獸”的同學(xué)看到這題都應(yīng)該非常容易理解了，“游戲也不過(guò)是這樣寫出來(lái)的”O(∩_∩)O哈~
?
題意不難懂，我大致翻譯一下：
就是要求把一個(gè)冰壺從起點(diǎn)“2”用最少的步數(shù)移動(dòng)到終點(diǎn)“3”
其中0為移動(dòng)區(qū)域，1為石頭區(qū)域，冰壺一旦想著某個(gè)方向運(yùn)動(dòng)就不會(huì)停止，也不會(huì)改變方向（想想冰壺在冰上滑動(dòng)），除非冰壺撞到石頭1 或者 到達(dá)終點(diǎn) 3
?
注意的是：
冰壺撞到石頭后，冰壺會(huì)停在石頭前面，此時(shí)（靜止?fàn)顟B(tài)）才允許改變冰壺的運(yùn)動(dòng)方向，而該塊石頭會(huì)破裂，石頭所在的區(qū)域由1變?yōu)?/span>0. 也就是說(shuō)，冰壺撞到石頭后，并不會(huì)取代石頭的位置。
終點(diǎn)是一個(gè)摩擦力很大的區(qū)域，冰壺若到達(dá)終點(diǎn)3，就會(huì)停止在終點(diǎn)的位置不再移動(dòng)。
?
解題思路：
其實(shí)與其說(shuō)這是深搜題，我覺(jué)得更像模擬題。。。
要先明確：
0為滑動(dòng)區(qū)域
1為石頭區(qū)域
2為起點(diǎn)，也是可滑動(dòng)區(qū)域
3為終點(diǎn)，不可滑動(dòng)區(qū)域
?
（1）?????? 起點(diǎn)為“2”，也是一個(gè)可滑動(dòng)的區(qū)域，所以標(biāo)記起點(diǎn)位置之后，可以把起點(diǎn)當(dāng)做0
（2）?????? 注意區(qū)分冰壺是運(yùn)動(dòng)的還是靜止的，若是靜止的話，旁邊1格有石頭是不能走的。
（3）?????? 輸出冰壺從2到3的最短路，如果最短路的步數(shù)大于10（不包括10），視作無(wú)法走到終點(diǎn)（其實(shí)這是用來(lái)剪枝的）
（4）?????? 滑動(dòng)過(guò)程中冰壺不允許出界
?
基于上面的原則，不難發(fā)現(xiàn)：（1）所謂的“走一步”，就是指冰壺從一個(gè)靜止?fàn)顟B(tài)到下一個(gè)靜止?fàn)顟B(tài)，就是說(shuō)冰壺在運(yùn)動(dòng)時(shí)經(jīng)過(guò)的“格數(shù)”不視作“步數(shù)”，也就是說(shuō)冰壺每次移動(dòng)的距離都是不定的。
（2）還有就是由于石頭會(huì)因?yàn)楸鶋氐呐鲎捕?#xff0c;因此冰壺每“走一步”，場(chǎng)地的環(huán)境就會(huì)改變一次。
（3）基于（2），可以發(fā)現(xiàn)本題雖然是要找 “最短路”，但是BFS幾乎不可能，因?yàn)槊俊白咭徊健?#xff0c;場(chǎng)地的狀態(tài)就要改變一次；而如果該步不滿足要求，又要求把場(chǎng)地的狀態(tài)還原到前一步，這只有DFS能做到。
（4）基于（3），DFS不是BFS，不能簡(jiǎn)單地用它來(lái)找最短路，必須要把所有可能的路一一找出來(lái)，再逐一比較它們的步數(shù)才能確定最短。但題目值允許1000MS，此時(shí)就面臨一個(gè)超時(shí)的問(wèn)題。所以題目才同時(shí)給出“步數(shù)超過(guò)10則視為失敗”的條件，這是用來(lái)剪枝的
?
有了上面的分析，就能最終確定本題的解法了：
有2種方法：
DFS+Vector+剪枝
DFS+回溯+剪枝
?
但是由于POJ對(duì)STL的“兼容性”很差，我用STL就沒(méi)見(jiàn)過(guò)不TLE的題。。。這題也一樣，所以不推薦，其實(shí)Vector是很好用的，利用它的特性可以在DFS返回上一步時(shí)，自動(dòng)還原場(chǎng)地狀態(tài)，而回溯法則需要手動(dòng)還原場(chǎng)地狀態(tài)（其實(shí)也就8行代碼）
?
DFS用于尋找路徑，回溯（或Vector）用于還原棋盤狀態(tài)，剪枝用于優(yōu)化
?
另外注意的時(shí)，如果把冰壺定義為“動(dòng)靜”兩種狀態(tài)，那么搜索時(shí)就可以以“格”為單位，+1搜索，詳細(xì)可以看我的程序，我感覺(jué)這樣比較簡(jiǎn)單。我感覺(jué)每步都用for找移動(dòng)的格數(shù)會(huì)非常煩
?
下面我會(huì)把兩種代碼都貼出來(lái)，供大家參考。
1 /*DFS+回溯+剪枝*/2
3 //Memory Time
4 //188K 329MS
5
6 #include<iostream>
7 using namespace std;
8
9 const int inf=11;
10
11 typedef class
12 {
13 public:
14 int r,c; //冰壺當(dāng)前位置
15 bool status; //status冰壺當(dāng)前狀態(tài)：運(yùn)動(dòng)true ,靜止false
16 }SE;
17
18 SE s,e; //記錄冰壺起止點(diǎn)
19 int w,h; //場(chǎng)地size
20 int MinStep; //最短路
21 int board[30][30]; //場(chǎng)地
22
23 void DFS(int i,int j,bool status,int direction,int step,bool flag)
24 { //direction:冰壺當(dāng)前運(yùn)動(dòng)方向 North:0 West:1 South:2 East:3
25 //flag:是否消除direction方向下一格位置的石頭
26
27 if(step>10) //剪枝，超過(guò)10步的走法就不再考慮了
28 return;
29
30 if(board[i][j]==3) //終點(diǎn)
31 {
32 if(MinStep>step)
33 MinStep=step;
34 return;
35 }
36
37 if(flag) //消除石頭
38 {
39 switch(direction)
40 {
41 case 0: {board[i-1][j]=0; break;}
42 case 1: {board[i][j-1]=0; break;}
43 case 2: {board[i+1][j]=0; break;}
44 case 3: {board[i][j+1]=0; break;}
45 }
46 }
47
48 if(!status) //靜止
49 {
50 if(i-1>=1 && (board[i-1][j]==0 || board[i-1][j]==3)) //North
51 DFS(i-1,j,true,0,step+1,false);
52
53 if(j-1>=1 && (board[i][j-1]==0 || board[i][j-1]==3)) //West
54 DFS(i,j-1,true,1,step+1,false);
55
56 if(i+1<=h && (board[i+1][j]==0 || board[i+1][j]==3)) //South
57 DFS(i+1,j,true,2,step+1,false);
58
59 if(j+1<=w && (board[i][j+1]==0 || board[i][j+1]==3)) //East
60 DFS(i,j-1,true,3,step+1,false);
61 }
62 else if(status) //運(yùn)動(dòng)
63 {
64 switch(direction)
65 {
66 case 0:
67 {
68 if(i-1<1) //預(yù)判下一步是否越界
69 return;
70 else
71 {
72 if(board[i-1][j]==0) //下一位置為0且不越界，繼續(xù)運(yùn)動(dòng)
73 DFS(i-1,j,true,0,step,false);
74 else if(board[i-1][j]==1) //下一位置為1且不越界，停止運(yùn)動(dòng)，并消除下一位置的石頭
75 DFS(i,j,false,0,step,true);
76 else if(board[i-1][j]==3) //下一位置為3且不越界，運(yùn)動(dòng)到位置3后停止運(yùn)動(dòng)，游戲結(jié)束
77 DFS(i-1,j,false,0,step,false);
78 }
79
80 break;
81 }
82 case 1:
83 {
84 if(j-1<1) //預(yù)判下一步是否越界
85 return;
86 else
87 {
88 if(board[i][j-1]==0) //下一位置為0且不越界，繼續(xù)運(yùn)動(dòng)
89 DFS(i,j-1,true,1,step,false);
90 else if(board[i][j-1]==1) //下一位置為1且不越界，停止運(yùn)動(dòng)，并消除下一位置的石頭
91 DFS(i,j,false,1,step,true);
92 else if(board[i][j-1]==3) //下一位置為3且不越界，運(yùn)動(dòng)到位置3后停止運(yùn)動(dòng)，游戲結(jié)束
93 DFS(i,j-1,false,1,step,false);
94 }
95
96 break;
97 }
98 case 2:
99 {
100 if(i+1>h) //預(yù)判下一步是否越界
101 return;
102 else
103 {
104 if(board[i+1][j]==0) //下一位置為0且不越界，繼續(xù)運(yùn)動(dòng)
105 DFS(i+1,j,true,2,step,false);
106 else if(board[i+1][j]==1) //下一位置為1且不越界，停止運(yùn)動(dòng)，并消除下一位置的石頭
107 DFS(i,j,false,2,step,true);
108 else if(board[i+1][j]==3) //下一位置為3且不越界，運(yùn)動(dòng)到位置3后停止運(yùn)動(dòng)，游戲結(jié)束
109 DFS(i+1,j,false,2,step,false);
110 }
111
112 break;
113 }
114 case 3:
115 {
116 if(j+1>w) //預(yù)判下一步是否越界
117 return;
118 else
119 {
120 if(board[i][j+1]==0) //下一位置為0且不越界，繼續(xù)運(yùn)動(dòng)
121 DFS(i,j+1,true,3,step,false);
122 else if(board[i][j+1]==1) //下一位置為1且不越界，停止運(yùn)動(dòng)，并消除下一位置的石頭
123 DFS(i,j,false,3,step,true);
124 else if(board[i][j+1]==3) //下一位置為3且不越界，運(yùn)動(dòng)到位置3后停止運(yùn)動(dòng)，游戲結(jié)束
125 DFS(i,j+1,false,3,step,false);
126 }
127
128 break;
129 }
130 }
131 }
132
133 if(flag) //回溯前還原石頭，即還原上一步的棋盤狀態(tài)
134 {
135 switch(direction)
136 {
137 case 0: {board[i-1][j]=1; break;}
138 case 1: {board[i][j-1]=1; break;}
139 case 2: {board[i+1][j]=1; break;}
140 case 3: {board[i][j+1]=1; break;}
141 }
142 }
143
144 return;
145 }
146
147 int main(void)
148 {
149 while(cin>>w>>h)
150 {
151 if(!w && !h)
152 break;
153
154 /*Structure the Board*/
155
156 MinStep=inf;
157
158 for(int i=1;i<=h;i++)
159 for(int j=1;j<=w;j++)
160 {
161 cin>>board[i][j];
162
163 if(board[i][j]==2)
164 {
165 s.r=i;
166 s.c=j;
167 s.status=false;
168 board[i][j]=0; //記錄起點(diǎn)位置后，把它作為0處理
169 }
170 if(board[i][j]==3) //終點(diǎn)是特別位置，冰壺經(jīng)過(guò)或到達(dá)該格都會(huì)停止
171 {
172 e.r=i;
173 e.c=j;
174 }
175 }
176
177 /*Search the min path*/
178
179 DFS(s.r , s.c , s.status , 0 , 0 , false);
180
181 if(MinStep<=10)
182 cout<<MinStep<<endl; //DFS里面雖然剪枝了，但是可能把全部走法都剪了，因此還是要判斷
183 else
184 cout<<-1<<endl;
185
186 }
187 return 0;
188 }
============華麗的分割線===============
?
1 /*DFS+Vector+剪枝*/2
3 //TLE
4 //萬(wàn)惡的POJ好像和STL不兼容，剪枝還是超時(shí)
5 //vector的優(yōu)勢(shì)無(wú)法發(fā)揮啊。。。
6
7 #include<iostream>
8 #include<vector>
9 using namespace std;
10
11 const int inf=11;
12
13 typedef class
14 {
15 public:
16 int r,c; //冰壺當(dāng)前位置
17 bool status; //status冰壺當(dāng)前狀態(tài)：運(yùn)動(dòng)true ,靜止false
18 }SE;
19
20 SE s,e; //記錄冰壺起止點(diǎn)
21 int w,h; //場(chǎng)地size
22 int MinStep; //最短路
23
24 void DFS(vector<vector<int> >board,int i,int j,bool status,int direction,int step,bool flag)
25 { //direction:冰壺當(dāng)前運(yùn)動(dòng)方向 North:0 West:1 South:2 East:3
26 //flag:是否消除direction方向下一格位置的石頭
27
28 if(step>10) //剪枝，超過(guò)10步的走法就不再考慮了
29 return;
30
31 if(board[i][j]==3) //終點(diǎn)
32 {
33 if(MinStep>step)
34 MinStep=step;
35 return;
36 }
37
38 if(flag) //消除石頭
39 {
40 switch(direction)
41 {
42 case 0: {board[i-1][j]=0; break;} //board用vector表示的目的就是為了在當(dāng)前步刪除某位置的石頭時(shí)
43 case 1: {board[i][j-1]=0; break;} //前一步并不會(huì)刪除該位置的石頭
44 case 2: {board[i+1][j]=0; break;}
45 case 3: {board[i][j+1]=0; break;}
46 }
47 }
48
49 if(!status) //靜止
50 {
51 if(i-1>=1 && (board[i-1][j]==0 || board[i-1][j]==3)) //North
52 DFS(board,i-1,j,true,0,step+1,false);
53
54 if(j-1>=1 && (board[i][j-1]==0 || board[i][j-1]==3)) //West
55 DFS(board,i,j-1,true,1,step+1,false);
56
57 if(i+1<=h && (board[i+1][j]==0 || board[i+1][j]==3)) //South
58 DFS(board,i+1,j,true,2,step+1,false);
59
60 if(j+1<=w && (board[i][j+1]==0 || board[i][j+1]==3)) //East
61 DFS(board,i,j-1,true,3,step+1,false);
62 }
63 else if(status) //運(yùn)動(dòng)
64 {
65 switch(direction)
66 {
67 case 0:
68 {
69 if(i-1<1) //預(yù)判下一步是否越界
70 return;
71 else
72 {
73 if(board[i-1][j]==0) //下一位置為0且不越界，繼續(xù)運(yùn)動(dòng)
74 DFS(board,i-1,j,true,0,step,false);
75 else if(board[i-1][j]==1) //下一位置為1且不越界，停止運(yùn)動(dòng)，并消除下一位置的石頭
76 DFS(board,i,j,false,0,step,true);
77 else if(board[i-1][j]==3) //下一位置為3且不越界，運(yùn)動(dòng)到位置3后停止運(yùn)動(dòng)，游戲結(jié)束
78 DFS(board,i-1,j,false,0,step,false);
79 }
80
81 break;
82 }
83 case 1:
84 {
85 if(j-1<1) //預(yù)判下一步是否越界
86 return;
87 else
88 {
89 if(board[i][j-1]==0) //下一位置為0且不越界，繼續(xù)運(yùn)動(dòng)
90 DFS(board,i,j-1,true,1,step,false);
91 else if(board[i][j-1]==1) //下一位置為1且不越界，停止運(yùn)動(dòng)，并消除下一位置的石頭
92 DFS(board,i,j,false,1,step,true);
93 else if(board[i][j-1]==3) //下一位置為3且不越界，運(yùn)動(dòng)到位置3后停止運(yùn)動(dòng)，游戲結(jié)束
94 DFS(board,i,j-1,false,1,step,false);
95 }
96
97 break;
98 }
99 case 2:
100 {
101 if(i+1>h) //預(yù)判下一步是否越界
102 return;
103 else
104 {
105 if(board[i+1][j]==0) //下一位置為0且不越界，繼續(xù)運(yùn)動(dòng)
106 DFS(board,i+1,j,true,2,step,false);
107 else if(board[i+1][j]==1) //下一位置為1且不越界，停止運(yùn)動(dòng)，并消除下一位置的石頭
108 DFS(board,i,j,false,2,step,true);
109 else if(board[i+1][j]==3) //下一位置為3且不越界，運(yùn)動(dòng)到位置3后停止運(yùn)動(dòng)，游戲結(jié)束
110 DFS(board,i+1,j,false,2,step,false);
111 }
112
113 break;
114 }
115 case 3:
116 {
117 if(j+1>w) //預(yù)判下一步是否越界
118 return;
119 else
120 {
121 if(board[i][j+1]==0) //下一位置為0且不越界，繼續(xù)運(yùn)動(dòng)
122 DFS(board,i,j+1,true,3,step,false);
123 else if(board[i][j+1]==1) //下一位置為1且不越界，停止運(yùn)動(dòng)，并消除下一位置的石頭
124 DFS(board,i,j,false,3,step,true);
125 else if(board[i][j+1]==3) //下一位置為3且不越界，運(yùn)動(dòng)到位置3后停止運(yùn)動(dòng)，游戲結(jié)束
126 DFS(board,i,j+1,false,3,step,false);
127 }
128
129 break;
130 }
131 }
132 }
133
134 return;
135 }
136
137 int main(void)
138 {
139 while(cin>>w>>h)
140 {
141 if(!w && !h)
142 break;
143
144 /*Structure the Board*/
145
146 MinStep=inf;
147 vector<vector<int> >board(h+1,vector<int>(w+1));
148
149 for(int i=1;i<=h;i++)
150 for(int j=1;j<=w;j++)
151 {
152 cin>>board[i][j];
153
154 if(board[i][j]==2)
155 {
156 s.r=i;
157 s.c=j;
158 s.status=false;
159 board[i][j]=0; //記錄起點(diǎn)位置后，把它作為0處理
160 }
161 if(board[i][j]==3) //終點(diǎn)是特別位置，冰壺經(jīng)過(guò)或到達(dá)該格都會(huì)停止
162 {
163 e.r=i;
164 e.c=j;
165 }
166 }
167
168 /*Search the min path*/
169
170 DFS(board , s.r , s.c , s.status , 0 , 0 , false);
171
172 if(MinStep<=10)
173 cout<<MinStep<<endl; //DFS里面雖然剪枝了，但是可能把全部走法都剪了，因此還是要判斷
174 else
175 cout<<-1<<endl;
176
177 /*Relax*/
178
179 // board.swap(vector<vector<int> >()); //POJ好像禁用swap()
180 }
181 return 0;
182 }
?
?
轉(zhuǎn)載于:https://www.cnblogs.com/lyy289065406/archive/2011/07/31/2122371.html
總結(jié)
以上是生活随笔為你收集整理的POJ3009-Curling 2.0的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
- 上一篇： javascript,jquery 操作
- 下一篇： 排序算法以及其应用