太空站之迷解題報(bào)告

1、太空站之迷解題報(bào)告上海市 復(fù)旦附中 張寧無(wú)論誰(shuí)第一眼看完這道題，都會(huì)覺(jué)得題目似乎太另類(lèi)，使人感到摸不著頭腦，與現(xiàn)有的經(jīng)典算法都是風(fēng)馬牛不相及的。并且再深入地想一想，發(fā)覺(jué)即使給一個(gè)小數(shù)據(jù)讓人來(lái)手工判斷都不是一件容易的事，題目中若是在太空站中毫無(wú)目的的亂走一氣是不可能得到任何有用的信息的，而且還存在迷失方向的危險(xiǎn)。并且可能出現(xiàn)的情況又多得讓人無(wú)從著手，更別說(shuō)讓計(jì)算機(jī)來(lái)一一判斷了。照這樣一說(shuō)，難道題目真的難得不可做。那到不是，但是我們需要從題目中尋求突破口。這樣，先讓我們從題目的描述中尋找出一些有價(jià)值的信息吧！首先，題目中告訴我們所有未知物質(zhì)連成一片，這個(gè)條件在絲毫沒(méi)有思路時(shí)無(wú)法給我們?nèi)魏螏椭?，但?/p>

2、我們可以明白一點(diǎn)，在真空格中不會(huì)出現(xiàn)類(lèi)似“孤島”的未知物質(zhì)。另外，太空站內(nèi)沒(méi)有“狹窄的通道”，這個(gè)條件提供的信息也對(duì)我們沒(méi)有實(shí)質(zhì)的幫助。題目中還告訴我們，機(jī)器人只可能被送到與某個(gè)未知物質(zhì)有公共邊的格子，這是一個(gè)有利用價(jià)值的條件（當(dāng)我們看完下一個(gè)條件時(shí)就會(huì)體會(huì)到）。另一個(gè)重要的條件是，任意傳送門(mén)周?chē)?個(gè)格子中不會(huì)有其他傳送門(mén)或者未知物質(zhì)，并且傳送門(mén)是成對(duì)的。那樣，當(dāng)我們找到一個(gè)傳送門(mén)的時(shí)候，我們就可以肯定它周?chē)?個(gè)格子都沒(méi)有傳送門(mén)。再注意到，一個(gè)傳送門(mén)周?chē)遣粫?huì)有未知物質(zhì)的，那么未知物質(zhì)周?chē)囊蝗吘壎疾粫?huì)出現(xiàn)傳送門(mén)，當(dāng)然初始時(shí)，機(jī)器人便處在邊緣的一個(gè)格子上，我們還可以肯定“貼著邊”走一定不

3、會(huì)誤入傳送門(mén)。當(dāng)然光靠這些來(lái)解題是不夠的，我們應(yīng)當(dāng)自己從題目中挖掘條件，考慮到在沒(méi)有未知物質(zhì)與傳送門(mén)的真空格上行走時(shí)，向東南西北四個(gè)方向任走一格我們?nèi)匀豢梢詮姆捶较蛟吠嘶兀?dāng)我們通過(guò)傳送門(mén)時(shí)，我們發(fā)現(xiàn)我們也可以原路退回，這使得當(dāng)我們通過(guò)向某些方向行進(jìn)后，雖然我們可能不知道此時(shí)身處何方，我們?nèi)匀豢梢酝ㄟ^(guò)向這些方向的反方向行進(jìn)來(lái)退回到出發(fā)點(diǎn)，也就是說(shuō)，在太空站中所有路徑都是可逆的。這一個(gè)條件至關(guān)重要，解題時(shí)自使至終我們都要依靠這個(gè)條件來(lái)說(shuō)明問(wèn)題。1234567891011121314151617181920212223當(dāng)我們從12向北走入7后，我們?nèi)钥上蚰贤嘶氐?2。當(dāng)我們從12向東通過(guò)傳送門(mén)1

4、3-10，到達(dá)11后，我們?nèi)钥上蛭魍ㄟ^(guò)傳送門(mén)13-10，回到12當(dāng)我們從12向北走入7后，我們?nèi)钥上蚰贤嘶氐?2。當(dāng)我們從12向東通過(guò)傳送門(mén)13-10，到達(dá)11后，我們?nèi)钥上蛭魍ㄟ^(guò)傳送門(mén)13-10，回到12我們可以確定當(dāng)我們?cè)谝粭l不經(jīng)過(guò)傳送門(mén)的路徑上行進(jìn)時(shí)可以達(dá)到預(yù)計(jì)的目的地，也就是說(shuō)，當(dāng)我們?cè)诓缓瑐魉烷T(mén)的真空格上行走時(shí)可以像在普通地圖上行走一樣，每一步我們都能夠確定機(jī)器人的方位。即使我們走入一個(gè)可能為傳送門(mén)的方格，迷失了方位，我們也可以原路再退回來(lái)。有了這些分析，我們應(yīng)該可以對(duì)題目有些思路了。我們可以考慮是否能夠通過(guò)試探每一個(gè)真空格來(lái)確定傳送門(mén)的位置。我們將太空站中所有的方格分成四類(lèi)，第一類(lèi)

5、是未知物質(zhì)，第二類(lèi)是已探明不是傳送門(mén)的方格（第一類(lèi)方格的周?chē)吘壎际堑诙?lèi)方格），第三類(lèi)是已探明為傳送門(mén)的方格，第四類(lèi)就是為探明的方格。當(dāng)然由于一個(gè)傳送門(mén)周?chē)?個(gè)方格都不是傳送門(mén)，因此一個(gè)第三類(lèi)方格周?chē)际堑诙?lèi)方格，且第一類(lèi)方格是連通的，因此，我們也可以簡(jiǎn)單地得到結(jié)論所有第二類(lèi)方格都是連通的，即我們可以確定地從地圖上任意一個(gè)第二類(lèi)方格行進(jìn)到另一個(gè)第二類(lèi)方格（不經(jīng)過(guò)傳送門(mén)，每一步都是可以預(yù)計(jì)的）。1234567891011121314151617181920212223第四類(lèi)第一類(lèi)第二類(lèi)那么，當(dāng)然每一次最好只試探一個(gè)第四類(lèi)方格，否則的話，就很難判斷到底在哪一格走入了傳送門(mén)，或者也可能通過(guò)幾個(gè)傳

6、送門(mén)，這樣一來(lái)，就無(wú)法判斷了。我們可以發(fā)現(xiàn)編號(hào)最小的第四類(lèi)方格（如上圖中的第10號(hào)方格）的西邊和北邊都是第二類(lèi)方格，因此我們可以從這個(gè)方格的西邊進(jìn)入，再向北邊走一格。當(dāng)這個(gè)方格不是傳送門(mén)時(shí)，機(jī)器人可以準(zhǔn)確無(wú)誤地走到4號(hào)方格，否則便不可能達(dá)到4號(hào)方格（10-13是一對(duì)傳送門(mén)，事實(shí)上機(jī)器人到達(dá)了9號(hào)方格），那么我們所要做的便是驗(yàn)證機(jī)器人是否到達(dá)了4號(hào)方格。由于編號(hào)最小的第四類(lèi)方格北方一定是第二類(lèi)方格，因此，若是我們對(duì)所有已探明的第二類(lèi)方格都設(shè)計(jì)一系列的行動(dòng)方案使得只有機(jī)器人從此方格出發(fā)才能夠完成這一系列的行動(dòng)。在上圖中為了要驗(yàn)證是否到達(dá)了4號(hào)方格，我們可以假設(shè)機(jī)器人在4號(hào)方格，那么機(jī)器人一定可以從

7、4號(hào)方格出發(fā)沿一定的路線繞著第一類(lèi)方格的邊緣饒行一周，若是機(jī)器人真的在4號(hào)方格那它一定能夠順利地行進(jìn)而不會(huì)受到阻礙（由moverobot的反饋值可以得到是否受到阻礙）。例如，路線：東北東南西南南東南西西西西西北北東東北東，可以使在4號(hào)的機(jī)器人完成路線：4512651116172322212019181278934，而在9號(hào)方格的機(jī)器人則完成不了這一系列的移動(dòng)：9149142019遇到未知物質(zhì)，在其他方格也是同樣不可能實(shí)現(xiàn)的。因此我們就有了思路，若是機(jī)器人能夠完成預(yù)定的移動(dòng)，則說(shuō)明機(jī)器人經(jīng)過(guò)的第四類(lèi)上沒(méi)有傳送門(mén)，則我們將其劃分到第二類(lèi)方格，若是不能完成，則我們將其劃分到第三類(lèi)方格，而它周?chē)?個(gè)

8、方格中的第四類(lèi)方格都將劃分到第二類(lèi)。但是，我們還需解決兩個(gè)問(wèn)題，一個(gè)是如何確定機(jī)器人當(dāng)前的位置，還有一點(diǎn)就是如何對(duì)每一個(gè)方格制定確定的路線。確定位置時(shí)，有兩種情況：一種時(shí)未經(jīng)過(guò)傳送門(mén)，這一種比較好處理，因?yàn)槲覀冎灰ＷC所有指定的路線都是回路（回到出發(fā)點(diǎn)），這樣當(dāng)機(jī)器人驗(yàn)證完自己所處的位置時(shí)，機(jī)器人就已經(jīng)回到了驗(yàn)證時(shí)的出發(fā)點(diǎn)，我們只需再向南行進(jìn)一格再向北行進(jìn)一格，我們就退回到了出發(fā)點(diǎn)；第二種是經(jīng)過(guò)了傳送門(mén)，我們其實(shí)也可以根據(jù)路徑的可逆性，將所進(jìn)行的一系列行動(dòng)逆序并反向執(zhí)行，便可以退回到驗(yàn)證時(shí)的出發(fā)點(diǎn)，也只要向南行進(jìn)一格再向北行進(jìn)一格，我們就退回到了出發(fā)點(diǎn)。當(dāng)然也就確定了所處的位置。指定路線，應(yīng)該

9、遵循兩個(gè)原則，每一個(gè)第二類(lèi)方格的路線是唯一的，第二個(gè)是路線不能夠無(wú)限制的長(zhǎng)（畢竟要考慮到moverobot的次數(shù)），基于以上兩個(gè)原則，我們來(lái)指定路線。我們先對(duì)于初始的邊緣區(qū)域的方格制定路線為饒著邊緣行進(jìn)一周(用貼邊走的方法來(lái)搜索邊緣)，但是我們?nèi)匀徊荒鼙ＷC對(duì)于每個(gè)數(shù)據(jù)都能唯一確定，我們需要加一些舉措來(lái)確保正確性，因此我們可以在行進(jìn)過(guò)程中故意向未知物質(zhì)走去，就可以試探當(dāng)前位置是否在邊緣（這類(lèi)試探不需很多，畢竟最多只有5對(duì)傳送門(mén)），例如在向順時(shí)針?lè)较蜣D(zhuǎn)彎時(shí)，向前多走一步，此時(shí)（moverobot的反饋值若是沒(méi)有受阻礙反而說(shuō)明機(jī)器人因?yàn)榻?jīng)過(guò)傳送門(mén)而沒(méi)有到達(dá)預(yù)定的方格）。而其他第四類(lèi)方格擴(kuò)展出來(lái)的第二

10、類(lèi)方格，由于是逐個(gè)擴(kuò)展，方格的北邊與西邊一定有一個(gè)第二類(lèi)方格，那么，我們只需在其基礎(chǔ)上添加兩步即可。例如，若是新擴(kuò)展出的方格北邊是一個(gè)以制定路線的第二類(lèi)方格，則我們可以將路線制定為先向北走一格，再按北邊的方格的路線行進(jìn)一周，再向南退回，由于已制定的方格的路線都是回路，那么新擴(kuò)展的方格的路線也一定是回路，且由于北邊方格的路線唯一確定，那么新擴(kuò)展的方格的路線也是唯一確定的。若第二類(lèi)方格只有在西邊，則也是類(lèi)似的情況。我們完成了對(duì)一個(gè)第四類(lèi)方格的探索，就需要對(duì)下一個(gè)符合要求的第四類(lèi)方格加以探索，至于這一步，我們是由確定位置到達(dá)確定位置（所有第二類(lèi)方格都是連通的），用搜索當(dāng)然可以得到路徑，但是我們可以利

11、用已求得的信息來(lái)確定路徑而不需再進(jìn)行搜索，由于每一個(gè)第二類(lèi)方格的路線都要沿著邊緣饒一圈，因此任意兩個(gè)第二類(lèi)方格的路線都有重合部分，那么我們只要將兩個(gè)方格的路徑加以合并，便可以得到兩個(gè)第二類(lèi)方格之間的路徑。我們已經(jīng)可以完成試探每個(gè)第四類(lèi)方格的步驟，只要我們將每個(gè)第四類(lèi)方格都試探完，剩下最后的一步工作就是確定所有傳送門(mén)之間的對(duì)應(yīng)。這一點(diǎn)與探索第四類(lèi)方格有些類(lèi)似，由于我們從一個(gè)確定的傳送門(mén)的一邊進(jìn)入，一定會(huì)到達(dá)另一個(gè)未知傳送門(mén)的另一邊，那么我們只要對(duì)所有其他傳送門(mén)的另一邊的方格一一做試探，就可以確定到底與哪一個(gè)傳送門(mén)相對(duì)應(yīng)。至此，算法的所有部分都討論完了。我們可以從著道題的解題過(guò)程中體會(huì)到遇到新問(wèn)題

12、切忌驚慌，看清楚題目，將題意分析透徹，從題目中找到啟發(fā)和提示，這樣對(duì)于我們做題是很有幫助的。附源程序：（最大的地圖moverobot的次數(shù)也應(yīng)在10000以內(nèi)）uses robot;const inp=station.dat; w:array0.3,1.2 of -1.1=(-1,0),(0,1),(1,0),(0,-1); z:array0.3 of char=(N,E,S,W);var n,m,k,u,v,x0,y0,x1,y1,xs,ys:integer; a,r:array1.15,1.15 of integer; c:array1.15,1.15,0.100 of shortint;

13、 d,e:array1.100 of shortint; f:array1.10,1.2 of shortint;procedure search(x,y,z:integer);var i,j,o,p,q:integer;begin if (x=x0) and (y=y0) then exit; rx,y:=0;inc(u); if ax+wz,1,y+wz,2=0 then begin if ax+w(z+1) mod 4,1,y+w(z+1) mod 4,2=0 then begin eu:=(z+1) mod 4-10;inc(u);eu:=(z+2) mod 4; search(x+w

14、(z+2) mod 4,1,y+w(z+2) mod 4,2,(z+1) mod 4); end else begin eu:=(z+1) mod 4; search(x+w(z+1) mod 4,1,y+w(z+1) mod 4,2,z); end; end else begin eu:=z; search(x+wz,1,y+wz,2,(z+3) mod 4); end;end;procedure initialize;var i,j,p,q:integer; ch:char;begin assign(input,inp);reset(input); readln(n,m,k); v:=0;

15、 for i:=1 to n do begin for j:=1 to m do begin read(ch); if ch=* then begin ai,j:=0;ri,j:=0; end else begin inc(v);ai,j:=v;ri,j:=1; if ch=S then begin x0:=i;y0:=j; end; end; end; readln; end; close(input); for i:=1 to 4 do if (ax0+wi,1,y0+wi,2=0) and (ax0+w(i+1) mod 4,1,y0+w(i+1) mod 4,20) then brea

16、k; u:=1;e1:=(i+1) mod 4;rx0,y0:=0; search(x0+w(i+1) mod 4,1,y0+w(i+1) mod 4,2,i); p:=x0;q:=y0;i:=1; while i=u do begin cp,q,0:=u; for j:=i to u do cp,q,j-i+1:=ej; for j:=1 to i-1 do cp,q,u-i+j+1:=ej; while ei0 then break; end; if x1=0 then begin move:=false;exit; end; move:=true; if (x1=xs) and (y1-

17、1=ys) then exit; for i:=1 to n do for j:=1 to m do bi,j:=-1; p:=x1;q:=y1-1; for i:=1 to cx1,y1-1,0 do if cx1,y1-1,i=0 then begin bp,q:=cx1,y1-1,i; p:=p+wcx1,y1-1,i,1;q:=q+wcx1,y1-1,i,2; end; p:=xs;q:=ys; while bp,q=-1 do begin o:=1; while cp,q,o0 do inc(o); i:=cp,q,1;j:=moverobot(zi); p:=p+wi,1;q:=q

18、+wi,2; end; while (px1) or (qy1-1) do begin i:=bp,q;j:=moverobot(zi); p:=p+wi,1;q:=q+wi,2; end; xs:=x1;ys:=y1-1;end;function test(x,y:integer):boolean;var i,j,o,p,q:integer;begin q:=0; for i:=1 to cx,y,0 do if cx,y,i0 then begin rp,q:=0; cp,q,0:=cp+wui,1,q+wui,2,0+2; cp,q,1:=ui; for j:=1 to cp,q,0-2

19、 do cp,q,j+1:=cp+wui,1,q+wui,2,j; cp,q,cp,q,0:=(ui+2) mod 4; end; end;end;procedure solve;var i,j,u:integer;begin while move(1) do begin j:=moverobot(z1); j:=moverobot(z0); if test(x1-1,y1) then begin rx1,y1:=0; cx1,y1,0:=cx1,y1-1,0+2; cx1,y1,1:=3; for i:=1 to cx1,y1-1,0 do cx1,y1,i+1:=cx1,y1-1,i; c

20、x1,y1,cx1,y1,0:=1; end else begin rx1,y1:=-1; pk(x1,y1); end; j:=moverobot(z2); j:=moverobot(z3); end; u:=0; for i:=1 to n do for j:=1 to m do if ri,j=-1 then begin inc(u);fu,1:=i;fu,2:=j; end; while move(-1) do begin j:=moverobot(z1); rx1,y1:=-2; for i:=1 to u do if rfi,1,fi,2=-1 then if test(fi,1,

21、fi,2+1) then begin answer(ax1,y1,afi,1,fi,2); rfi,1,fi,2:=-2;break; end; j:=moverobot(z3); end;end;begin init; initialize; solve;end.下面是我自己做的一個(gè)robot.tpu的庫(kù)：unit robot;interfaceprocedure init;function moverobot(direction:char):integer;procedure answer(pos1,pos2:integer);implementationconst in1=station

22、.dat; in2=station.lnk; out=station.log;var n,m,k,u,v,x,y,er:integer; t:longint; a:array1.15,1.15 of integer; b:array1.225,0.3 of integer;procedure init;var i,j,p,q:integer; ch:char;begin assign(input,in1);reset(input); readln(n,m,k); t:=0;u:=0;v:=0;er:=0; for i:=1 to n do begin for j:=1 to m do begin read(ch); if ch=* then ai,j:=0 else begin inc(v);ai,j:=v; bv,0:=v;bv,1:=i;bv,2:=j;bv,3:=0; if ch=S then begin x:=i;y:=j; end; end; end; readln; end; close(input); assign(input,in2);reset(input); for i:=1 to k do