搞了半天八數碼弄不出來就只好來打題解 這道題是在搜索a碰到的(鏈接: http://pan.baidu.com/s/1jG9rQsQ ) 感覺題目最大亮點就是這英文簡寫"ni", 真是令人感慨出題老師的才華啊 好了，廢話不多說 題目內容如下（閒煩請無視之，下下方有簡單的介紹):
【問題描述】
貝 西（Bessie）在卡摩洛遇到了棘手的情況：她必須穿越由Ni騎士把守的森林。 騎士答應Bessie
只要 Bessie 能給他們帶來一叢灌木就能安全穿越森林。時間寶貴，Bessie 必須盡快找到一叢灌木
然後給騎士送去。
Bessie有一張森林的地圖。森林被劃分成了W×H個網格（1≤W≤1000; 1≤H≤1000）。 每 個
網格用0～4的整數表示。
0：可以通行；
1：無法通行（沼澤、懸崖、殺手） ；
2：Bessie的起始位置；
3：騎士的起始位置；
4：灌木叢。
Bessie 只能朝上下左右四個方向行走，每走一個網格要花一天的時間，請超出一條到達騎士的
最短路。問題保證有解。
【輸入】
輸入文件的第一行是W和H；
一般來講，後面有 H 行每行 W 個整數（即 0～4），表示地圖。但是當某行的整數個數超過 40 個
時，就會另起一行。
【輸出】
輸出Bessie至少需要幾天才能把灌木叢帶給騎士。
【輸入樣例】
8 4
4 1 0 0 0 0 1 0
0 0 0 1 0 1 0 0
0 2 1 1 3 0 4 0
0 0 0 4 1 1 1 0
【輸出樣例】
11
【Hint】
Explanation of the sample: Width=8, height=4. Bessie starts on the third row, only a few squares away from the Knights.
Bessie can move in this pattern to get a shrubbery for the Knights: N, W, N, S, E, E, N, E, E, S, S. She gets the
shrubbery in the northwest corner and then makes her away around the barriers to the east and then south to
the Knights.
題目內容一大堆,說簡單點就是給出一張W*H（1<=W,H<=1000）的地圖，每個位置都標有0..4的數字。其中0表示可以通過，1表示不能通過，2表示Bessie的起始位置，3表示騎士起始位置，4表示樹叢。現在要求求出一條最短的路，使騎士經過樹叢至少一次，且能夠到達Bessie所在位置。
一開始看到題目認為這個好簡單啊 不就是一個裸的bfs嗎 於是就開始打了第一遍代碼 打了之後發現思路很混亂 往哪兒開始搜索都搞不清 於是再看題目 這一看就明白了 就是題中的單精度小女孩(......)要去找它的騎士大哥（666......)當然，這位小女孩還要經過一個樹叢柑橘（這不是廢話嗎)
這給人第一感覺就是從樹叢開始往girl和boy搜素 用一個s數組保存到某個點的最小距離 一開始值設置成0 然後從第一個樹開始一個個搜過去 每搜一次保存最小值 也就是s[a1][b1]+s[a2][b2](a1,b1,a2,b2分別是girl和boy的坐標位置 當然這裡也需要注意一下如果沒有搜到的話 bfs也是會退出的 這樣的話相應s數組的值也可能還是0 這裡就要加一個特判 也就是當兩個s的值都不等於0時才進行 （一開始答案輸出老是0 看到這裡把數據輸出來才知道被坑了 所以說數組返回值有風險（適當的賓語前置。），使用需謹慎。
好像又講開了，那麼我們還是回歸正題。(啊，正題是什麼......) 好，這樣幾遍的bfs之後樣例就能正確輸出了 （好高興啊） 過程代碼如下：
1 void bfs(int a,int b)
2 {
3 s[a][b]=1;
4 q[1].push(a);
5 q[2].push(b);
6 q[3].push(0);
7 while((!q[1].empty())&&(!q[2].empty())&&(!q[3].empty()))
8 {
9 for(int d=1;d<=4;d++)
10 {
11 int x=q[1].front()+dx[d];
12 int y=q[2].front()+dy[d];
13 if(g[x][y]==1||x<1||x>h||y<1||y>w)
14 continue;
15 if(s[x][y]==0)
16 {
17 s[x][y]=q[3].front()+1;
18 // cout<<"x "<<x<<' '<<"y "<<y<<endl;
19 // cout<<"s "<<s[x][y]<<endl;
20 sum2++;
21 q[1].push(x);
22 q[2].push(y);
23 q[3].push(s[x][y]);
24 if(s[a1][b1]>0&&s[a2][b2]>0)
25 {
26 // cout<<s[a1][b1]<<' '<<s[a2][b2]<<endl;
27 return;
28 }
29 }
30 }
31 q[1].pop();
32 q[2].pop();
33 q[3].pop();
34 }
35 }
然後去測 只過了8個點 （很郁悶 這難道不是bfs嗎 再看看數據100w 應該能過嘛 ）但再看 我這裡的不止是一次bfs 而是對於每個草叢都要來一次bfs 復雜度就由此極大的提高了 有沒有辦法剪枝呢?
於是我會教室又去想 終於在眼保健操的時候有了一點靈感： 既然問題的一方面出在對於每個樹都搜過去而造成了某種意義上的超時 那麼我們是不是可以在這裡加個條件以減少bfs的次數呢? 如果當前搜的書與起點終點的曼哈頓距離已經比minn大了 那麼
無論怎麼走都不可能了 和以前做的一道售貨員的難題的剪枝像 然後，看到了教室前面開著的電腦 內心想著：反正才第一節嘛 還有時間 於是我就飛奔地上去測了 果然原來6s跑出來的第九個點 這次只要1.3s了 呵呵，然後記得那節晚讀整個人都好了
可是 ，1.3s只是較以前的6s有了一些較大的改進 但還遠遠不夠
那麼，再接著想：既然我在bfs的做之前加了這麼一個條件 那麼 在bfs內部拓展節點的時候是不是也可以試著加個類似的條件呢? 仔細想想bfs的“原理” 它是從近往遠的每一排節點進行拓展的 也就是說 下一次取隊頭出來的肯定是要比這次大的 好 那麼在有了理論依據和現實基礎後 我果斷的在進行是否拓展過的判斷之前加了這樣一個條件
問題似乎迎刃而解了 再去測 第九個點終於闖入了1s大關 0.7! 再懷著興奮的心情去搞第十個點時 答案卻也再沒有顯示出來了 (好憂傷......)
於是我又再想 假如他數據前面幾次的minn是很大但又遞減的呢 這樣的話我在bfs前的判斷不久跟沒做過一樣嘛 WTF! 但轉念一想 數據是死的但人是活的嘛 於是我就想干脆對每個樹枝對於其道起點終點的曼哈頓距離進行排序 如下圖所示：
然後終於 第十個點在教室0.7s跑出來了!!!!! （記得我後來高興了一節歷史課） 然後去機房測 0.3 好了，這道題就在機房終於a掉了
順便發表一下我的感慨：真的感覺最後把這題做出來很有成就感 每一次改進都是一次小的躍進 oi或許正是需要這種不懈的探索精神吧
難道故事就這樣結束了嗎?(Q:有的人認為這句話也可以去掉但也有人說不可以去掉 你認為呢? A:這句話承上啟下 起到了過渡的作用 同時亦吸引了讀者的閱讀興趣 (666...))
好講到這裡我便先把前面的ac代碼放出來給大家看看 (由於配置不夠 在家測要1s+ 請勿見怪 本文最後亦會提及一種更好的方法）
1 #include<iostream>
2 #include<cstdio>
3 #include<queue>
4 #include<cstring>
5 #include<ctime>
6 #include<cmath>
7 #include<algorithm>
8 #include<cstring>
9 using namespace std;
10 const int maxn=750+10;
11 struct node
12 {
13 int x,y;
14 }data[maxn];
15 int g[maxn][maxn],s[maxn][maxn];
16 int dx[5]={0,1,0,-1,0};
17 int dy[5]={0,0,1,0,-1};
18 int w,h,cnt=0,sum1=0,sum2=0;
19 int a1,b1,a2,b2,k1;
20 int s1,s2,minn=0x7f7f7f;
21 queue<int>q[4];
22 int distance1(int a,int b)
23 {
24 return (abs(a1-a)+abs(a2-a)+abs(b1-b)+abs(b2-b));
25 }
26 void bfs(int a,int b)
27 {
28 sum1++;
29 // queue<int>q[4];
30 s[a][b]=1;
31 q[1].push(a);
32 q[2].push(b);
33 q[3].push(0);
34 while((!q[1].empty())&&(!q[2].empty())&&(!q[3].empty()))
35 {
36 for(int d=1;d<=4;d++)
37 {
38 int x=q[1].front()+dx[d];
39 int y=q[2].front()+dy[d];
40 if(g[x][y]==1||x<1||x>h||y<1||y>w)
41 continue;
42 if(distance1(x,y)>minn)
43 continue;
44 if(s[x][y]==0)
45 {
46 s[x][y]=q[3].front()+1;
47 // cout<<"x "<<x<<' '<<"y "<<y<<endl;
48 // cout<<"s "<<s[x][y]<<endl;
49 sum2++;
50 q[1].push(x);
51 q[2].push(y);
52 q[3].push(s[x][y]);
53 if(s[a1][b1]>0&&s[a2][b2]>0)
54 {
55 // cout<<s[a1][b1]<<' '<<s[a2][b2]<<endl;
56 return;
57 }
58 }
59 }
60 q[1].pop();
61 q[2].pop();
62 q[3].pop();
63 }
64 }
65 bool my_comp(node a,node b)
66 {
67 return (distance1(a.x,a.y)<distance1(b.x,b.y));
68 }
69 int main()
70 {
71 ios::sync_with_stdio(false);
72 // freopen("ni.in","r",stdin);
73 // freopen("ni.out","w",stdout);
74 freopen("1.in","r",stdin);
75 // freopen("1.out","w",stdout);
76 cin>>w>>h;
77 for(int i=1;i<=h;i++)
78 for(int j=1;j<=w;j++)
79 {
80 cin>>g[i][j];
81 if(g[i][j]==2)
82 {
83 a1=i;
84 b1=j;
85 }
86 if(g[i][j]==3)
87 {
88 a2=i;
89 b2=j;
90 }
91 if(g[i][j]==4)
92 {
93 k1++;
94 data[k1].x=i;
95 data[k1].y=j;
96 }
97 }
98 // for(int i=1;i<=h;i++)
99 // {
100 // for(int j=1;j<=w;j++)
101 // cout<<g[i][j]<<' ';
102 // cout<<endl;
103 // }
104 // cout<<g[2][1]<<endl;
105 // cout<<g[2][1]<<endl;
106 // for(int i=1;i<=h;i++)
107 // for(int j=1;j<=w;j++)
108 // if(g[i][j]==4)
109 sort(data+1,data+k1+1,my_comp);
110 for(int i=1;i<=k1;i++)
111 {
112 if(distance1(data[i].x,data[i].y)>minn)
113 continue;
114 while((!q[1].empty())&&(!q[2].empty())&&(!q[3].empty()))
115 {
116 if(!q[1].empty())
117 q[1].pop();
118 if(!q[2].empty())
119 q[2].pop();
120 if(!q[3].empty())
121 q[3].pop();
122 }
123 // cout<<i<<' '<<j<<endl;
124 // while(!q[1].empty())
125 // q[1].pop();
126 // while(!q[2].empty())
127 // q[2].pop();
128 // while(!q[3].empty())
129 // q[3].pop();
130
131 memset(s,0,sizeof(s));
132 bfs(data[i].x,data[i].y);
133 // cout<<s[a1][b1]<<' '<<s[a2][b2]<<endl;
134 if(s[a1][b1]!=0&&s[a2][b2]!=0&&s[a1][b1]+s[a2][b2]<minn)
135 minn=s[a1][b1]+s[a2][b2];
136 }
137 // cout<<sum1<<' '<<sum2<<endl;
138 cout<<minn<<endl;
139 // cout << "\n" << (double)clock() / CLOCKS_PER_SEC;
140 // cout<<sum<<endl;
141 return 0;
142 }
好了，以上是我的代碼 做完後我又去問了一下yyl學長 又獲得了一些啟示： 1.這道題用手工隊列比STL裡的要來的快 突出表現在不需要用一個while 一遍遍的彈隊列 直接改一下head和tail 就行了 2.事實上我在改進之後的bfs次數減少了很多(453次bfs，515269次拓展）但事實上並不需要這麼多次bfs 只需要從起點和終點開始統計出每個樹叢到起點和終點的最少步數 最後對每個樹叢統計就好了 3.山外有山，碼外有碼 或許換種方式 算法會有更大的改進
另外 ，至於最後yyl學長提出的改進 我將會盡量在明天給出代碼 現在真的太困了 得先睡覺了
好了 ，起床 ，開更
對於上面說的方法我剛剛又再敲了一遍 從girl和boy出發 全圖遍歷至所有的樹叢都找到為止 在這裡需要一個判斷 由於才疏學淺我就直接線性遍歷數組了
對了 還有一點就是代碼中的bfs過程中可以直接引用數組的參數 但我弄了半天都不行(*s ? s[ ]) 於是我就直接重新copy了一遍過程(弱弱的氣息......)
但實際上可以用hash 康托展開等方法來實現之 這些的話等我以後有時間再把代碼補上吧 家裡電腦(配置很爛,當年機房0.2s的家裡跑了3s)勉強1s能過 如右圖所示：
代碼如下：
1 #include<iostream>
2 #include<cstdio>
3 #include<queue>
4 #include<cstring>
5 #include<ctime>
6 #include<cmath>
7 #include<algorithm>
8 #include<cstring>
9 using namespace std;
10 const int maxn=750+10;
11 struct node
12 {
13 int x,y;
14 }data[maxn];
15 int g[maxn][maxn],s1[760][760],s2[760][760];
16 int dx[5]={0,1,0,-1,0};
17 int dy[5]={0,0,1,0,-1};
18 int w,h,cnt=0,sum1=0,sum2=0;
19 int a1,b1,a2,b2,k1,k2;
20 int minn=0x7f7f7f;
21 queue<int>q[4];
22 int distance1(int a,int b)
23 {
24 return (abs(a1-a)+abs(a2-a)+abs(b1-b)+abs(b2-b));
25 }
26 bool all1()
27 {
28 for(int i=1;i<=k1;i++)
29 if(s1[data[i].x][data[i].y]==0)
30 return false;
31 return true;
32 }
33 bool all2()
34 {
35 for(int i=1;i<=k1;i++)
36 if(s2[data[i].x][data[i].y]==0)
37 return false;
38 return true;
39 }
40 void bfs1(int a,int b)
41 {
42 // sum1++;
43 // queue<int>q[4];
44 s1[a][b]=1;
45 q[1].push(a);
46 q[2].push(b);
47 q[3].push(0);
48 while((!q[1].empty())&&(!q[2].empty())&&(!q[3].empty()))
49 {
50 for(int d=1;d<=4;d++)
51 {
52 int x=q[1].front()+dx[d];
53 int y=q[2].front()+dy[d];
54 if(g[x][y]==1||x<1||x>h||y<1||y>w)
55 continue;
56 // if(distance1(x,y)>minn)
57 // continue;
58 if(s1[x][y]==0)
59 {
60 s1[x][y]=q[3].front()+1;
61 // cout<<"x "<<x<<' '<<"y "<<y<<endl;
62 // cout<<"s "<<s[x][y]<<endl;
63 // sum2++;
64 q[1].push(x);
65 q[2].push(y);
66 q[3].push(s1[x][y]);
67 if(all1())
68 {
69 // cout<<s[a1][b1]<<' '<<s[a2][b2]<<endl;
70 return;
71 }
72 }
73 }
74 q[1].pop();
75 q[2].pop();
76 q[3].pop();
77 }
78 }
79 void bfs2(int a,int b)
80 {
81 // sum1++;
82 // queue<int>q[4];
83 s2[a][b]=1;
84 q[1].push(a);
85 q[2].push(b);
86 q[3].push(0);
87 while((!q[1].empty())&&(!q[2].empty())&&(!q[3].empty()))
88 {
89 for(int d=1;d<=4;d++)
90 {
91 int x=q[1].front()+dx[d];
92 int y=q[2].front()+dy[d];
93 if(g[x][y]==1||x<1||x>h||y<1||y>w)
94 continue;
95 // if(distance1(x,y)>minn)
96 // continue;
97 if(s2[x][y]==0)
98 {
99 s2[x][y]=q[3].front()+1;
100 // cout<<"x "<<x<<' '<<"y "<<y<<endl;
101 // cout<<"s "<<s[x][y]<<endl;
102 // sum2++;
103 q[1].push(x);
104 q[2].push(y);
105 q[3].push(s2[x][y]);
106 if(all2())
107 {
108 // cout<<s[a1][b1]<<' '<<s[a2][b2]<<endl;
109 return;
110 }
111 }
112 }
113 q[1].pop();
114 q[2].pop();
115 q[3].pop();
116 }
117 }
118 bool my_comp(node a,node b)
119 {
120 return (distance1(a.x,a.y)<distance1(b.x,b.y));
121 }
122 int main()
123 {
124 ios::sync_with_stdio(false);
125 freopen("ni.in","r",stdin);
126 freopen("ni.out","w",stdout);
127 // freopen("1.in","r",stdin);
128 // freopen("1.out","w",stdout);
129 cin>>w>>h;
130 for(int i=1;i<=h;i++)
131 for(int j=1;j<=w;j++)
132 {
133 cin>>g[i][j];
134 if(g[i][j]==2)
135 {
136 a1=i;
137 b1=j;
138 }
139 if(g[i][j]==3)
140 {
141 a2=i;
142 b2=j;
143 }
144 if(g[i][j]==4)
145 {
146 k1++;
147 data[k1].x=i;
148 data[k1].y=j;
149 }
150 }
151 bfs1(a1,b1);
152 while((!q[1].empty())&&(!q[2].empty())&&(!q[3].empty()))
153 {
154 if(!q[1].empty())
155 q[1].pop();
156 if(!q[2].empty())
157 q[2].pop();
158 if(!q[3].empty())
159 q[3].pop();
160 }
161 bfs2(a2,b2);
162 for(int i=1;i<=k1;i++)
163 {
164 if(s1[data[i].x][data[i].y]!=0&&s2[data[i].x][data[i].y]!=0)
165 minn=min(minn,s1[data[i].x][data[i].y]+s2[data[i].x][data[i].y]);
166 }
167 cout<<minn<<endl;
168 // for(int i=1;i<=h;i++)
169 // {
170 // for(int j=1;j<=w;j++)
171 // cout<<g[i][j]<<' ';
172 // cout<<endl;
173 // }
174 // cout<<g[2][1]<<endl;
175 // cout<<g[2][1]<<endl;
176 // for(int i=1;i<=h;i++)
177 // for(int j=1;j<=w;j++)
178 // if(g[i][j]==4)
179 // sort(data+1,data+k1+1,my_comp);
180 // for(int i=1;i<=k1;i++)
181 // {
182 // if(distance1(data[i].x,data[i].y)>minn)
183 // continue;
184 // while((!q[1].empty())&&(!q[2].empty())&&(!q[3].empty()))
185 // {
186 // if(!q[1].empty())
187 // q[1].pop();
188 // if(!q[2].empty())
189 // q[2].pop();
190 // if(!q[3].empty())
191 // q[3].pop();
192 // }
193 //// cout<<i<<' '<<j<<endl;
194 //// while(!q[1].empty())
195 //// q[1].pop();
196 //// while(!q[2].empty())
197 //// q[2].pop();
198 //// while(!q[3].empty())
199 //// q[3].pop();
200 //
201 // memset(s,0,sizeof(s));
202 // bfs(data[i].x,data[i].y);
203 //// cout<<s[a1][b1]<<' '<<s[a2][b2]<<endl;
204 // if(s[a1][b1]!=0&&s[a2][b2]!=0&&s[a1][b1]+s[a2][b2]<minn)
205 // minn=s[a1][b1]+s[a2][b2];
206 // }
207 // // cout<<sum1<<' '<<sum2<<endl;
208 // cout<<minn<<endl;
209 // cout << "\n" << (double)clock() / CLOCKS_PER_SEC;
210 // cout<<sum<<endl;
211 return 0;
212 }
