【題2】最少步數(shù)

1、 1 / 5 【題2】最少步數(shù) 問題描述 在各種棋中，棋子的走法總是一定的，如中國象棋中馬走“日”。有一位小學(xué)生就想如果馬能有兩種走法將增加其趣味性，因此，他規(guī)定馬既能按“日”走，也能如象一樣走“田”字。他的同桌平時喜歡下圍棋，知道這件事后覺得很有趣，就想試一試，在一個（19*19）的圍棋盤上任選兩點 A、B，A點放上黑子，B點放上白子，代表兩匹馬。棋子可以按“日”字走，也可以按“田”字走，倆人一個走黑馬，一個走白馬。誰用最少的步數(shù)走到左上角坐標(biāo)為(1,1)的點時，誰獲勝?，F(xiàn)在他請你幫忙，給你 A、B兩點的坐標(biāo)，想知道兩個位置到（1,1）點的可能最少步數(shù)。 樣例 輸入： 12 16 18 10

2、 輸出： 89 題解 由于 A、B兩點是隨機輸入的，因此無法找到計算最少步數(shù)的數(shù)學(xué)規(guī)律，只能通過廣度優(yōu)先搜索的辦法求解。 1、確定出發(fā)點 從（x,y）出發(fā)通過一次廣度優(yōu)先搜索，可以找到從(x,y)至棋盤上所有可達(dá)點的最少步數(shù)。而問題中要求的是黑馬所在的（x 2 / 5 1，y 1）和白馬所在（x 2，y 2）到達(dá)(1,1)目標(biāo)點的最少步數(shù)。雖然兩條路徑的起點不一樣，但是它們的終點卻是一樣的。如果我們將終點(1,1)作為起點，這樣只需要一次廣度優(yōu)先搜索便可以得到（x 1，y 1）和（x 2，y 2）到達(dá)(1,1)的最少步數(shù)。 2、數(shù)據(jù)結(jié)構(gòu)設(shè)que隊列，存儲從(1,1)可達(dá)的點（quek, 1.2

3、）以及到達(dá)該點所需要的最少步數(shù)（quek,3）（0k192 +1）。隊列的首指針為closed，尾指針為open。初始時，que中只有一個元素為(1,1)，最少步數(shù)為 0。 S記錄(1,1)到每點所需要的最少步數(shù)。顯然，問題的答案是sx 1,y 2和sx 2,y 2。初始時，s1,1為0，除此之外的所有元素值設(shè)為- 1。為了使得馬從棋盤內(nèi)任意位置擴展出的坐標(biāo)均在s的范圍內(nèi)，我們將s數(shù)組的范圍擴大至s- 3 / 5 1.21,- 1.21。 dx、dy移動后的位置增量數(shù)組。馬有12種不同的擴展方向： 馬走“日”： (x-2,y-1)(x-1,y-2)(x-2,y+1)(x-1,y+2)(x+2,

4、y-1)(x+1,y-2)(x+2,y+1)(x+1,y+2)馬走“田”： (x-2,y-2)(x-2,y+2)(x+2,y-2)(x+2,y+2) 我們將i方向上的位置增量存入常量數(shù)組dxi、dyi中（1i12） const dx： array 1.12 of integer=(-2,-2,-1,1,2,2,2,2,1,-1,-2,-2); dy： array 1.12 of integer=(-1,-2,-2,-2,-2,-1,1,2,2,2,2,1); 3、約束條件 不能越出界外。由于馬的所有可能的落腳點s均在s的范圍內(nèi)，因此一旦馬越出界外，就將其s值賦為0，表示“已經(jīng)擴展過，且(1,1

5、)到達(dá)其最少需要0步”。這看上去是荒謬的，但可以簡單而有效地避免馬再次落入這些界外點。 該點在以前的擴展中沒有到達(dá)過。如果曾經(jīng)到達(dá)過，則根據(jù)廣度優(yōu)先搜索的原理，先前到達(dá)該點所需的步數(shù)一定小于當(dāng)前步數(shù)，因此完全沒有必要再擴展下去。 由此得出，馬的跳后位置（x,y）是否可以入隊的約束條件是sx,y<0 4 / 5 4、算法流程 fillchar(s,sizeof(s),0); s1,10; s數(shù)組的初始化for x11 to 19 do for y11 to 19 do sx1,y1-1; fillchar(que,sizeof(que),0); 隊列初始化open1;closed0; 初始

6、位置入隊que1,11;que1,21; read(x1,y1,x2,y2); 讀入黑馬和白馬的出發(fā)位置while closed<open do 若隊列非空，則擴展隊首結(jié)點begin inc(closed); for d1 to 12 do 枚舉8個擴展方向begin xqueclosed,1+dxd; 計算馬按d方向跳躍后的位置yqueclosed,2+dyd; if sx,y<0 then 若（x,y）滿足約束條件begin sx,yqueclosed,3+1; 計算(1,1)到(x,y)的最少步數(shù)inc(open); （x,y）和（1,1）至（x,y）的最少步數(shù)入隊queopen,1x; queopen,2y; queopen,