迷宫,这题用广度优先搜索(BFS)怎么做?
pascal吧
全部回复
仅看楼主
level 6
摩摩专答 楼主
描述 迷宫的管理员们决定在新开始的季节里使用新的墙纸。出于这个目的他们需要一个程序来计算迷宫内墙壁的面积。这就是你即将要做的工作。 我们把这个迷宫用一个N*N (3 <= N <= 33) 的矩阵表示。一些矩阵单元包含一个 “ .” (这代表一个空的方块),另一些矩阵单元包含一个“ #” (这代表一个用巨石砌成的石墙占据的方块)。全部方块的大小都为 3*3 平方米。
墙壁由迷宫的四周(除了作为迷宫出入口的左上角和右下角以外)以及那些标记为“ #” 的矩阵单元构成,除此之外没有其他的墙。在输入的矩阵里左上角和右下角永远是一个“ .”。 你的任务是计算迷宫里可见部分的墙壁的面积。换句话说,就是对迷宫的游客来说墙壁表面可见的部分。注意在两块相邻的石块之间没有空隙,即使两块石块在转角处相接触,我们都认为它们是相邻的。看看图示的例子:迷宫中可见的墙壁都用加粗的线条来描画。所有墙壁的高度都是三米。
输入格式
输入的第一行包含一个数字N。接下来的N行每行都包含有N个字符。每行描述了迷宫矩阵的一行。每行都只有“ .” 、“ #” 这两个字符并都以一个换行符结束。输入里没有任何的空格
输出格式
你的程序必须输出一个整数,即所需要的壁纸的准确面积。
样例输入 5 ..... ...## ..#.. ..### .....
样例输出 198
2013年08月14日 00点08分 1
level 6
摩摩专答 楼主
没有高手进来么
2013年08月14日 02点08分 2
level 6
摩摩专答 楼主
更正一下
样例输入:
5
.....
...##
..#..
..###
.....
样例输出:
198
2013年08月14日 02点08分 3
level 2
var n,i,j:longint; p:int64;
s:ansistring;
a:array[0..34,0..34] of string;
b:array[0..34,0..34] of 0..1;
procedure search(x:longint; y:longint);
begin
b[x,y]:=1;
if (b[x-1,y]=0) and (a[x-1,y]='.') then search(x-1,y);
if (b[x+1,y]=0) and (a[x+1,y]='.') then search(x+1,y);
if (b[x,y-1]=0) and (a[x,y+1]='.') then search(x,y-1);
if (b[x,y+1]=0) and (a[x,y+1]='.') then search(x,y+1);
end;
begin
assign(input,'maze.in'); reset(input);
assign(output,'maze.out'); rewrite(output);
readln(n);
for i:=1 to n do
begin
readln(s);
for j:=1 to n do a[i,j]:=s[j];
end;
search(1,1);
search(n,n);
for i:=1 to n do begin b[0,i]:=0; b[i,0]:=0; b[n+1,i]:=0; b[i,n+1]:=0; end;
for i:=1 to n do
for j:=1 to n do
begin
if b[i,j]=1 then
begin
if b[i-1,j]=0 then inc(p);
if b[i+1,j]=0 then inc(p);
if b[i,j-1]=0 then inc(p);
if b[i,j+1]=0 then inc(p);
end;
end;
writeln((p-4)*9);
close(input); close(output);
end.
2020年07月23日 00点07分 4
1