【正文】 ）的格子（ px+x,py+y）為墻 Then 設(shè)相對位置（ px,py）為墻； If can中每個空地（ x,y）相對（ px,py）的格子（ px+x,py+y）為空地 Then 設(shè)相對位置（ px,py）為空地，（ px,py）的 4個相鄰位置進入 uk鏈（不重復(fù)） Else 取 uk鏈的下一個相對位置 }； 搜索 uk鏈的每個相對位置（ px,py）：（ find(xx,yy)） { 累計 can中每個空地（ x,y）相對（ px,py）的格子（ px+x,py+y）中墻的總數(shù) d1和空地總數(shù) d2，將 │ d1d2│ 最小的相對位置記為（ xx， yy），并從 uk鏈中刪除該相對位置 }； 使用寬度優(yōu)先搜索方法尋找（ xx， yy）至（ nowx,nowy）的最短路徑，按照這條路徑確定移動和探索方案，并將 can鏈中不符探索結(jié)果的方格刪除； (path(nowx,nowy,xx,yy)。按照最小的要求排除，可以使每一次的探索盡量多的縮小初始位置的范圍，使程序盡量減少對運氣的依賴。S39。E39。 /*四個方向?qū)?yīng)的字母 */ st1=39。 /*后繼頂點的數(shù)組下標(biāo) */ end。O39。 /*已知信息組成的新地圖 ,z[x,y]存儲相對于當(dāng)前起點 (x,y)位置的狀態(tài)： 39。—(x,y)有墻； 39?！?x,y)已放入 uk鏈； ’ p?— (x,y)已標(biāo)記 */ uk,can:^arr。 /*探索前的準(zhǔn)備 */ start。 /*使用寬度優(yōu)先搜索方法尋找（ nextx,nexty）至（ nowx,nowy）的移動和探索方案，并將 can鏈中不符探索結(jié)果的方格刪除 */ }。/*main*/ readp過程：讀入城市地圖 a proc readp。reset(f)。/*for*/ close(f)。 { for i←1 to 4 do /* 判斷 (xx,yy)的四個相鄰方格 */ if z[xx+c[i,1],yy+c[i,2]]=39。 with uk^[tail]do { x←xx+c[i,1]。 /*隊尾指針 +1*/ }。nowy←0。 z[0,0]← 39。 /* 所有空地置入 can鏈表 */ for i←1 to u do for j←1 to v do if a[i,j]=39。y←j。 /*can 鏈尾的后繼指針為空 */ new(uk)。 /*將起點相鄰的四個方格放入 uk鏈 */ }。 while uk^[i].nexttail do /*沿 next指針取出 uk鏈中的每一個相對位置 (px,py)*/ { px←uk^[uk^[i].next].x。 /* 移后位置的狀態(tài)初始化，沿 can鏈計算確定狀態(tài)的方格 */ while (d3) and (can^[j].next0) do { j←can^[j].next。 /* 記錄該方格可能無墻 */ }。/* 移后位置可能有墻 */ if d=2 then { z[px,py]←39。/* 若 can鏈中的所有空地相對 (px,py)的方格狀態(tài)未確定，則取 uk鏈的下一個相對位置 */ }。 /*對運氣的最小的依賴度為 min*/ { min←maxint。 d1←0。W39。 o←i。 /* 搜索 uk的下一個相對位置 */ }。 var p:arr。p[1].next←0。O39。 z[p[t].x,p[t].y]← 39。 /*出隊 */ }。 move(d[i])。nowy←p[l].y。 /* 按照探索結(jié)果標(biāo)記（ x2,y2）的狀態(tài) */ if e=39。P39。 /* 刪除 can鏈中與探索結(jié)果不符的元素 */ while can^[j].next0 do/*若未搜索到鏈尾，則取出當(dāng)前相鄰的兩個鏈指針 */ { k←j。j←k }。但是，有些問題選擇單一的數(shù)據(jù)結(jié)構(gòu)會顧此失彼。 數(shù)據(jù)結(jié)構(gòu)的 “ 并聯(lián) ” 將用多個數(shù)據(jù)結(jié)構(gòu)應(yīng)用于同一數(shù)據(jù)集合的方法叫做數(shù)據(jù)結(jié)構(gòu)的并聯(lián)，這種數(shù)據(jù)結(jié)構(gòu)的結(jié)合方式不僅可以將多種存儲結(jié)構(gòu)的優(yōu)點完全發(fā)揮了出來，而且還可以通過映射建立不同數(shù)據(jù)結(jié)構(gòu)中元素間的對應(yīng)關(guān)系。 任務(wù) :給出一開始猴子們的情況和每一時刻松開手的情況 (必須保證每只抓住其它猴子尾巴的手松開且僅松開一次 )，要求計算每只猴子落地的時間。 (圖 (b))中頂點旁的數(shù)字給出了對應(yīng)猴子落地的時間。這樣，能夠方便的枚舉集合中的元素、合并并查集。 var n,i,j,k,t:longint。 /*初始時猴子間的連接情況為 tree， 添邊過程中生成的樹為 m。 /*答案，其中猴子 i的落地時間為time[i]*/ { readln(n)。l39。 /*讀時間數(shù) */ for i←1 to t do /* 依次讀入每個時刻的松手情況 */ { readln(j,ch,ch)。 /* 記錄時刻 i松手的猴子編號和左右手標(biāo)志 */ fillchar(m,sizeof(m),0)。open[i]^.next←nil。m[k,3]←e[i,1]。 while pnil do{ time[p^.v]←i。 closed[k]←nil。,time[i])}.{main} 數(shù)據(jù)結(jié)構(gòu)并聯(lián)方式的利弊 數(shù)據(jù)結(jié)構(gòu)支持的操作分為兩類： ⑴詢問操作：顧名思義，就是獲取該數(shù)據(jù)結(jié)構(gòu)記錄的某些信息的操作，而并沒有改動數(shù)據(jù)結(jié)構(gòu)里的元素及其相互關(guān)系。 數(shù)據(jù)結(jié)構(gòu)的并聯(lián)過程中，有時需要通過映射建立不同數(shù)據(jù)結(jié)構(gòu)中元素間的對應(yīng)關(guān)系。 初始時 v0進入第一組， v0的距離值為 0；第二組包含其它所有結(jié)點，這些結(jié)點對應(yīng)的距離值這樣確定（設(shè) vi為第二組中的結(jié)點） 然后每次從第二組的結(jié)點中選一個其距離值為最小的結(jié)點 vm加到第一組中。顯然，這種從第二組的結(jié)點中選距離值最小的結(jié)點擴展是一種貪心策略。通常情況下，邊數(shù) |E|都不小于頂點數(shù)|V|，所以運行時間又可以簡化為 O(ElgV)。 該算法的條件是該圖所有邊的權(quán)值非負(fù)，因此約定：對于每條邊 (u,v)E， w(u,v)≥0 。 Dijkstra算法每次尋找一條最短路徑時，需要兩個步驟： ⑴使用貪心策略，找一個不在最短路徑起點集合內(nèi)、并且到終點距離最短的頂點 i。 解決方案：采用映射的方法，將線性結(jié)構(gòu)中的元素與堆中的頂點一一對應(yīng)起來，若線性的數(shù)組中的元素發(fā)生變化，堆中相應(yīng)的頂點也隨之變化；堆中的頂點發(fā)生變化，數(shù)組中相應(yīng)的元素也隨之變化。 ⑵進行松弛操作，修改從與 i相鄰的頂點到終點的路徑長度。需要在矩陣中尋找一條從起始位置到終止位置的路徑 (可沿上下左右四個方向 )，并且要求路徑中經(jīng)過的所有數(shù)字，其相鄰數(shù)字之差的絕對值之和最小。但實現(xiàn)相當(dāng)繁瑣，在較短的時間里基本上不大可能寫出程序并調(diào)試好。綠色的結(jié)點為第一組的結(jié)點，灰色的結(jié)點為第二組的結(jié)點 Dijkstra算法的執(zhí)行速度取決于優(yōu)先隊列的數(shù)據(jù)結(jié)構(gòu) 用一維數(shù)組來實現(xiàn)優(yōu)先隊列 Q=VS：算法運行時間為 O(V2+E)=O(V2)。修改后再選距離值最小的一個結(jié)點加入到第一組中， … 。 Dijkstra算法 思維方向： 每次延長最短路時選擇權(quán)最小的邊，并調(diào)整最短路外每個結(jié)點至出發(fā)結(jié)點的路長 步驟： 把圖中所有結(jié)點分為兩組，每一個結(jié)點對應(yīng)一個距離值： 第一組：包括已確定最短路徑的結(jié)點，結(jié)點對應(yīng)的距離值是由 v0到此結(jié)點的最短路徑長度； 第二組：包括尚未確定最短路徑的結(jié)點，結(jié)點對應(yīng)的距離值 是 v0經(jīng)由第一組結(jié)點（中間結(jié)點）至此結(jié)點的最短路徑長度； 我們按最短路徑長度遞增的順序把第二組的結(jié)點加到第一組中去，直至 v0可達的所有結(jié)點都包含于第一組。 對于這兩類操作，數(shù)據(jù)結(jié)構(gòu)的并聯(lián)方式有利有弊。/*for*/ for i←1 to n do /* 輸出每個猴子的落地時間 */ if time[i]0 then writeln(i,39。/*then*/ closed[j]^.next←open[k]。 /* 從父頂點出發(fā)沿父指針追溯祖先頂點 */ while m[j,3]0 do j←m[j,3]。 for i←t downto 1 do /* 倒推時間，將每個時刻斷開的邊連上 */ { k←tree[e[i,1],e[i,2]]。 /*初始時樹空，每個猴子的落地時間為 0 */ for i←1 to n do /* 為每個猴子建立并查集 */ { new(open[i])。l39。/* 根據(jù)左右手確定 i為 j的左兒子還是右兒子 */ tree[i,3]←j }。 for i←2 to n do /* 依次讀入每個猴子的連接情況 */ { readln(j,ch,ch)。 /*松手情況，其中第 i時刻松手猴子的編號為 e[i,1]，松開手為 e[i,2](1—左手， 2—右手 )*/ open,closed:array [1..30000] of point。 /*左（ ‘ l?） 右 (?r?)手標(biāo)志 */ p:point。 /*并查集的鏈表指針類型 */ node=record /*鏈頂點類型 */ v:longint。 用并查集維護 當(dāng)并查集中某個集合加入編號為 1的點所在的集合時，需要把這個集合中的所有元素的時間記錄一下 (圖（ a） )。 4 把猴子抽象成頂點，猴子的手抽象成邊，則猴子們的連接情況構(gòu)成一個連通圖（圖（ a））題目就轉(zhuǎn)化成一個連通圖不斷去邊、求每個點離開編號為 1的點所在的連通分量的時間。每只猴子都有兩只手，編號為 1的猴子的尾巴掛在樹枝上，其它猴子的尾巴都被別的猴子的某只手抓著。多種數(shù)據(jù)結(jié)構(gòu)結(jié)合的方式一般有兩種 : ⑴ 數(shù)據(jù)結(jié)構(gòu)的 “ 并聯(lián) ” 。/*while*/ }。 if a[can^[j].x+x2,can^[j].y+y2]e /*若相對于 can[j]的（ x2,y2）位置的方格狀態(tài)與探索結(jié)果不符，則刪除 can[j]*/ then { dec(rest)。O39。 then changeUK(x2,y2)。 e←look(d[i])。j←p[l].next }。j←p[l].next。 /* 在地圖上標(biāo)記該相鄰格 */ p[t].next←s }。p[t].x←p[s].x+c[k,1]。t←1。 /*隊首指針為 s，隊尾指針為 t*/ { p[1].x←x2。/* 從 uk鏈中刪除依賴度運氣最小的相對位置 */ }。yy←py }。/*while*/ d2←rest d1。 while can^[j].next0 do /*在 can鏈表的每個空地相對于 (px,py)的方格中，累計墻的總數(shù) d1和空地的總數(shù) d2*/ { j←can^[j].next。/* 對運氣的最小依賴度初始化 ,從 uk鏈?zhǔn)组_始搜索 */ while uk^[i].nexttail do/*沿 next指針取出 uk鏈中的每一個相對位置 (px,py)*/ { px←uk^[uk^[i].next].x。/* change */ find：尋找對運氣的依賴度最小的相對位置 (xx,yy)，并將其從 uk鏈表中刪除 proc find(var xx,yy:integer)。changeUK(px,py) }。 if d=1 then z[px,py]←39。W39。 d←0。 var px,py,i,j,d:integer。uk^[0].next←1。/*with*/ }。 then{ inc(rest)。/* （ 0， 0）為無墻，其它位置未入 uk*/ new(can)。Q39。 var i,j:integer。 next←tail+1 }。 /*若 (xx