廣度優(yōu)先搜索.doc

《廣度優(yōu)先搜索.doc》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、廣度優(yōu)先搜索5、細胞(cell.pas)【問題描述】一矩形陣列由數(shù)字0到9組成,數(shù)字1到9代表細胞,細胞的定義為沿細胞數(shù)字上下左右還是細胞數(shù)字則為同一細胞,求給定矩形陣列的細胞個數(shù)。如陣列:0234500067103456050020456006710000000089有4個細胞。【輸入格式】整數(shù)m,n(m行，n列)矩陣【輸出格式】細胞的個數(shù)?！据斎霕永縞ell.in4100234500067103456050020456006710000000089【輸出樣例】cell.out4【參考程序】const???di:array[1..4]of-1..1=(0,0,-1,1);???dj:

2、array[1..4]of-1..1=(1,-1,0,0);varm,n:byte;???b:array[0..51,0..61]ofboolean;???que:array[1..3000]ofrecordi,j:byte;end;???num:word;procedureinit;vari,j:byte;???ch:char;begin???assign(input,'cell.in');reset(input);???fillchar(b,sizeof(b),false);???num:=0;???readln(m,n);???fori:=1tomdo???????begin???

3、????????forj:=1tondo???????????????begin???????????????????read(ch);???????????????????ifch<>'0'thenb[i,j]:=true;???????????????end;???????????readln;???????end;???close(input);end;{init}procedurefind(newi,newj:byte);vark:byte;???head,tail:word;begin???b[newi,newj]:=false;???inc(num);???withque[1

4、]dobegini:=newi;j:=newj;end;???head:=0;tail:=1;???repeat???????inc(head);???????fork:=1to4do???????????if(que[head].i+di[k]in[1..m])and(que[head].j+dj[k]in[1..n])and(b[que[head].i+di[k],que[head].j+dj[k]])then???????????????begin???????????????????inc(tail);???????????????????withque[tail]dobegin

5、i:=que[head].i+di[k];j:=que[head].j+dj[k];end;???????????????????b[que[tail].i,que[tail].j]:=false;???????????????end;???untilhead=tail;end;{find}procedurework;vari,j:byte;begin???fori:=1tomdo???????forj:=1tondo???????????ifb[i,j]thenfind(i,j);end;{work}procedureprint;begin???assign(output,'cell.

6、out');rewrite(output);???writeln(num);???close(output);end;{print;}begin{main}???init;???work;???print;end.6、營救【問題描述】鐵塔尼號遇險了！他發(fā)出了求救信號。距離最近的哥倫比亞號收到了訊息，時間就是生命，必須盡快趕到那里。通過偵測，哥倫比亞號獲取了一張海洋圖。這張圖將海洋部分分化成n*n個比較小的單位，其中用1標明的是陸地，用0標明是海洋。船只能從一個格子，移到相鄰的四個格子。為了盡快趕到出事地點，哥倫比亞號最少需要走多遠的距離?！据斎敫袷健康谝恍袨閚,下面是一個n*n的0、1矩

7、陣，表示海洋地圖最后一行為四個小于n的整數(shù)，分別表示哥倫比亞號和鐵塔尼號的位置?！据敵龈袷健扛鐐惐葋喬柕借F塔尼號的最短距離，答案精確到整數(shù)?！据斎霕永縮ave.in30011011001133【輸出樣例】save.out4【數(shù)據(jù)范圍】N<=1000【參考程序】const???dx:array[1..4]ofshortint=(1,-1,0,0);???dy:array[1..4]ofshortint=(0,0,-1,1);varn