资源描述：
《广度优先搜索.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、广度优先搜索5、细胞(cell.pas)【问题描述】一矩形阵列由数字0到9组成,数字1到9代表细胞,细胞的定义为沿细胞数字上下左右还是细胞数字则为同一细胞,求给定矩形阵列的细胞个数。如阵列:0234500067103456050020456006710000000089有4个细胞。【输入格式】整数m,n(m行，n列)矩阵【输出格式】细胞的个数。【输入样例】cell.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、营救【问题描述】铁塔尼号遇险了！他发出了求救信号。距离最近的哥伦比亚号收到了讯息，时间就是生命，必须尽快赶到那里。通过侦测，哥伦比亚号获取了一张海洋图。这张图将海洋部分分化成n*n个比较小的单位，其中用1标明的是陆地，用0标明是海洋。船只能从一个格子，移到相邻的四个格子。为了尽快赶到出事地点，哥伦比亚号最少需要走多远的距离。【输入格式】第一行为n,下面是一个n*n的0、1矩
7、阵，表示海洋地图最后一行为四个小于n的整数，分别表示哥伦比亚号和铁塔尼号的位置。【输出格式】哥伦比亚号到铁塔尼号的最短距离，答案精确到整数。【输入样例】save.in30011011001133【输出样例】save.out4【数据范围】N<=1000【参考程序】const dx:array[1..4]ofshortint=(1,-1,0,0); dy:array[1..4]ofshortint=(0,0,-1,1);varn
