Description - 問題描述
在各種棋中，棋子的走法總是一定的，如中國象棋中馬走“日”。有一位小學生就想如果馬能有兩種走法將增加其趣味性，因此，他規定馬既能按“日”走，也能如象一樣走“田”字。他的同桌平時喜歡下圍棋，知道這件事後覺得很有趣，就想試一試，在一個（100*100）的圍棋盤上任選兩點A、B，A點放上黑子，B點放上白子，代表兩匹馬。棋子可以按“日”字走，也可以按“田”字走，倆人一個走黑馬，一個走白馬。誰用最少的步數走到左上角坐標為(1,1)的點時，誰獲勝。現在他請你幫忙，給你A、B兩點的坐標，想知道兩個位置到（1,1）點可能的最少步數。
Input - 輸入數據
兩行：第一行A點的坐標，第二行B點的坐標，坐標都是不超過100的自然數。
Output - 輸出數據
兩行，第一行A點走到(1,1)位置的最少步數；第二行是B點走到(1,1)位置的最少步數。
詳細解法
讀完題目我們可以知道,這裡的馬可以走“日”字，亦可以走“田”字，那麼我們假設該點的坐標為(x,y)，那麼其可以到達的坐標便有12種情況，分別為：走“日”字：(x-2,y-1),(x-1,y-2),(x-2,y+1),(x-1,y+2),(x+2,y-1),(x+1,y-2),(x+1,y+2),(x+2,y+1);走“田”字：(x-2,y-2),(x-2,y+2),(x+2,y+2),(x+2,y-2)。這樣分析下來，我們便可將所有x的增量以及其所對應的y的增量保存到兩個數組dx[],dy[]中，每次通過對數組對應元素的選擇來完成移動。代碼如下：
int dx[12]={-2,-2,-1,1,2,2,2,2,1,-1,-2,-2};
int dy[12]={-1,-2,-2,-2,-2,-1,1,2,2,2,2,1};
其後，題目要求是分別有兩顆棋子進行移動，其最終目的地都是(1,1)，那麼，我們需要對每個棋子的移動方式進行探討嗎？其實不然，對於每一顆棋子，雖然他們的出發點不同，但其終點都為(1,1)。以是，我們便可看成是有一顆棋子從(1,1)出發，分別移動到(x1,y1),(x2,y2)的步數。這樣一來，便可以通過bfs（百度定義：寬度優先搜索算法（又稱廣度優先搜索）是最簡便的圖的搜索算法之一，這一算法也是很多重要的圖的算法的原型。Dijkstra單源最短路徑算法和Prim最小生成樹算法都采用了和寬度優先搜索類似的思想。其別名又叫BFS，屬於一種盲目搜尋法，目的是系統地展開並檢查圖中的所有節點，以找尋結果。換句話說，它並不考慮結果的可能位置，徹底地搜索整張圖，直到找到結果為止。）來完成整個的搜索最少步數的工作了。
既然確定了bfs的算法，那麼我們就需要使用隊列的結構了，我們可以用STL裡的queue來定義一個隊列數組，代碼如下：
#include<queue> queue<int>q[4];
其中，q[1]存儲從(1,1)可到達點的橫坐標，q[2]存儲從(1,1)可到達點的縱坐標，q[3]則表示到達該點所需要的最短步數。假如你說用不慣STL裡的queue，那麼我們也可以自己寫隊列，如下所示：
int que[maxn][4]={0};
同時也需要定義一個頭指針與一個尾指針，其二者的初值都為1，以表示隊列為空，代碼如下：
int head=1,tail=1;
其次，為了最後輸出的方便，我們還要定義一個s[maxn][maxn]數組來存儲到達s[x][y]的最小步數，最後只需要輸出s[x1][y1],s[x2][y2]的值即可。同時，也得將s[1][1]賦值為0，其他元素賦值為1，代碼如下：
memset(s,-1,sizeof(s)); s[1][1]=0;
（接下來，我們全部用自己寫的隊列，進行操作，使用STL代碼將在最後給出）
一開始，我們將初始狀態入隊，即q[1][1]=1,q[1][2]=1,q[1][3]=0，代碼如下：
q[1][1]=1;
q[1][2]=1;
q[1][3]=0;
接著，我們便使用一個循環進行拓展的操作，和1777的倒水一樣，循環成立的條件是head<=tail(即隊列不為空).然後，對於前面所列出的12種情況，我們每一種都要進行探討，即使用一個for循環，從0枚舉到11.其步驟大致如下：①取隊首元素所能到達的位置②判斷當前位置是否越界③判斷當前位置是否到達過（根據bfs的原理先前到達過的步數一定小於當前的步數，故不需要再繼續拓展）④將當前的s[x][y]的值更新，即其值就等於當前q[head][3]+1⑤將新得到的x，y的值入隊⑥判斷是否已將(x1,y1),(x2,y2)的最少步數都搜索到，即判斷s[x1][y1],s[x2][y2]的值是否都＞0，是的話就輸出後結束程序否則就彈出隊首元素（前面只是取出，並沒有彈出）並重復①。其代碼如下：
1 while(head<=tail)
2 {
3 for(int d=0;d<12;d++)
4 {
5 int x=q[head][1]+dx[d]; //取隊首元素所能到達橫坐標的位置
6 int y=q[head][2]+dy[d]; //取隊首元素所能到達縱坐標的位置
7 if(x>0&&y>0&&x<=100&&y<=100) //判斷是否在界內
8 if(s[x][y]==-1) //判斷是否已經拓展過
9 {
10 s[x][y]=q[head][3]+1; //更新s[x][y]的值
11 tail++; //將新狀態入隊
12 q[tail][1]=x;
13 q[tail][2]=y;
14 q[tail][3]=s[x][y];
15 if(s[x1][y1]>0&&s[x2][y2]>0) //判斷是否達到了目標狀態
16 {
17 cout<<s[x1][y1]<<endl; //輸出
18 cout<<s[x2][y2]<<endl;
19 return 0;
20 }
21 }
22 }
23 head++; //彈出隊首元素
24 }
最後，給出OJ上ac的代碼，僅供參考：
以下下為自己寫的隊列：
1 #include<iostream>
2 #include<cstring>
3 using namespace std;
4 int const maxn=10000+1;
5 int const area=100+1;
6 int dx[12]={-2,-2,-1,1,2,2,2,2,1,-1,-2,-2};
7 int dy[12]={-1,-2,-2,-2,-2,-1,1,2,2,2,2,1};
8 int s[area][area],q[maxn][4]={0};
9 int x1,y1,x2,y2;
10 int head=1,tail=1;
11 int main()
12 {
13 memset(s,0xff,sizeof(s));
14 cin>>x1>>y1>>x2>>y2;
15 q[1][1]=1;
16 q[1][2]=1;
17 q[1][3]=0;
18 while(head<=tail)
19 {
20 for(int d=0;d<12;d++)
21 {
22 int x=q[head][1]+dx[d]; //取隊首元素所能到達橫坐標的位置
23 int y=q[head][2]+dy[d]; //取隊首元素所能到達縱坐標的位置
24 if(x>0&&y>0&&x<=100&&y<=100) //判斷是否在界內
25 if(s[x][y]==-1) //判斷是否已經拓展過
26 {
27 s[x][y]=q[head][3]+1; //更新s[x][y]的值
28 tail++; //將新狀態入隊
29 q[tail][1]=x;
30 q[tail][2]=y;
31 q[tail][3]=s[x][y];
32 if(s[x1][y1]>0&&s[x2][y2]>0) //判斷是否達到了目標狀態
33 {
34 cout<<s[x1][y1]<<endl; //輸出
35 cout<<s[x2][y2]<<endl;
36 return 0;
37 }
38 }
39 }
40 head++; //彈出隊首元素
41 }
42 }
以下為直接用STL的隊列，其大致入隊出隊的操作都與前者相似，故不再介紹：
1 /*
2 Name: lwq
3 Copyright:
4 Author:
5 Date: 14-12-14 14:17
6 Description: 2226STL
7 */
8
9 #include<iostream>
10 #include<cstring>
11 #include<queue>
12 using namespace std;
13 int const maxn=10000+1;
14 int const area=100+1;
15 int dx[12]={-2,-2,-1,1,2,2,2,2,1,-1,-2,-2};
16 int dy[12]={-1,-2,-2,-2,-2,-1,1,2,2,2,2,1};
17 int s[area][area];
18 queue<int>q[4];
19 int x1,y1,x2,y2;
20 int main()
21 {
22 memset(s,-1,sizeof(s));
23 cin>>x1>>y1>>x2>>y2;
24 q[1].push(1);
25 q[2].push(1);
26 q[3].push(0);
27 while((!q[1].empty())&&(!q[2].empty())&&(!q[3].empty()))
28 {
29 for(int d=0;d<12;d++)
30 {
31 int x=q[1].front()+dx[d];
32 int y=q[2].front()+dy[d];
33 if(x>0&&y>0&&x<=100&&y<=100)
34 if(s[x][y]==-1)
35 {
36 s[x][y]=q[3].front()+1;
37 q[1].push(x);
38 q[2].push(y);
39 q[3].push(s[x][y]);
40 if(s[x1][y1]>0&&s[x2][y2]>0)
41 {
42 cout<<s[x1][y1]<<endl;
43 cout<<s[x2][y2]<<endl;
44 return 0;
45 }
46 }
47 }
48 q[1].pop();
49 q[2].pop();
50 q[3].pop();
51 }
52 }
最後，歡迎大家的指教。
