BFS宽搜（广度）c++

if (i

if (j=closed;

writeln('No answer!'); readln{输出无解} end; begin

writeln('Input x,y,z：'); readln(x,y,z); calc end.

【例题】房间问题。图4-9意示出了一张建筑平面图，编程计算：该建筑中有多少个房间；最大的房间有多大，拆除建筑中的某一堵墙，以形成一个尽可能大的房间，指出该墙。该建筑分成m*n割方块（m≤50，n≤50），每个方块可有0~4堵墙（0表示无墙）。 1 2 3 4 5 6 7 N 1 W E 2

S

图4-9 建筑平面图 3

输入数据：平面图以数字形式存储，用一个数字表示一个方块。 4 （1）文件开始是南北方向的方块数，其次是东西方向的方块数。 （2）后面的行中，每个方块中墙的特征由数字p来描述（0≤p≤15）。数字p是下面的可能取的数字之和：1（西墙west）2（北墙north）4（东墙east）8（南墙south）。 （3）建筑中至少有两个房间。例： 输入： 2 3

15 3 14 11 12 15

输出： 3 {三个房间}

4 {有四个方块} （1，1）（1，2） {拆除方格（1，1）（1，2）之间的墙} 【分析】该题要求根据建筑平面图中每个方块的墙的特征字得出：房间分布情况和求最佳拆墙方案。其中问题1的解是问题2的解的基础。因为只有计算出各房间拥有的方块数以及房间之间的隔墙情况，才能明确拆除那堵墙后可形成尽可能大的房间。

（1）明确每个方块中的设墙情况。程序从文件中输入m*n个0..15的数，每个数字描述了一个方块中墙的特征，即下面的可能取的数字之和：

1（西墙west）2（北墙north）3（东墙east）4（南墙south）

将方格中墙的特征字转换成一个四位二进制数，每一位对应一个方向的墙。

D3 D2 D1 D0 （2，1） 方向 ：南墙 东墙 北墙 西墙 方向数： 3 2 1 0 若DI位为1，表示该方格的I方向上有一堵墙；

若DI位为0，表示该方格的I方向上无墙，该方块与I方向上的相邻块同属一个房间（0≤I≤3），例如：（2，1）方块的墙的特征字为13， (11)10=(1011)2。即：（2,1）方块的墙的南面、北面、西面各有一堵墙。

（2）求房间的分布。虽然求出了每个方块中的设墙情况，但由于除周边外的中间方块中，每堵墙被位于墙两面的方块各定义一次，因此还不能得出有多少个房间，每个房间拥有那些

方块。接下来的问题是将建筑平面划分为若干连通的闭区域，这种区域亦称面。面有墙围成，两两面之间无公共方块。对每一面着一种序号的颜色，这个颜色序号对应该面内方块所在的房间序号。对建筑平面图的着色方案勾勒出建筑中房间的分布情况，其颜色数即为房间总数。 从（1,1）方块出发，由上而下、从左至右搜索一个目前未着色的块(x,y)。运用广度优先搜索的方法求（x,y）所在的面，对该面着一种新颜色。运用一次宽度优先搜索，可以确定一个面的所有方块，完成一个面着色。反复搜索，直到所有方块被着色时就求出了所有面。 （3）求最佳拆墙方案。有了房间的分布情况，求最佳拆墙方案便不难了，搜索最佳拆墙方案的算法如下：

设best：为目前最大房间的面积，搜索前初始化为0；按由上而下，由左至右搜索每一方块（i，j）的相邻格；若（I，j）与（I，j）k（0≤k≤1）方向的相邻块（x，y）分属两个房间且两个房间的面积之和大于best，则： best：（I，j）所属房间面积+（x，y）所属房间面积；记下两个方块（i，j）和（x，y）。 源程序如下： const

fn1 ='room.in'; fn2 ='room.out';

dig ：array[0..3] of integer=(1,2,4,8); {dig[I]——第[I]位二进制数的权} way ：array[0..3,1..2] of integer=((0,-1),(-1,0),(0,1),(1,0)); {way[I，1]——方向I的垂直增量；way[I，2]——方向I的水平增量} var

n,m ：integer; {n：平面图南北方向的长度，m：平面图东西方向的长度} total，max ：integer; {total为房间总数，max为最大房间包含的方块数}

x1,x2,x3,x4 ：integer; {表示应拆除方格（x1,x2）与方格（x3,x4）之间的那堵墙} a ：array[1..50,1..50,0..3] of boolean;

{0:west西墙} {1:north北墙} {2:east东墙} {3:south南墙}

{当a[I，j，k]为真时：方块（I，j）的k方向无墙，否则有墙} b ：array[1..50,1..50] of integer;

{若map[I，j]=0，则（I，j）方块未被检查过，否则为方块（I，j）所属的房间号} area ：array[1..2500] of integer; {area[I]：第I个房间的面积} list ：array[1..2500,1..2] of integer; {open表,closed表} procedure init;{输入} var

f ：text; i,j,k,p ：integer; begin

assign(f,fn1); reset(f); readln(f,n,m);

fillchar(a,sizeof(a),true);{初始化，假设所有方格四面无墙} for i：=1 to n do for j：=1 to m do begin

read(f,p);{读入特征字p} for k：=3 downto 0 do if p>=dig[k] then begin

a[i,j,k]：=false; dec(p,dig[k])

end {将特征字转换为四周设墙的情况} end; close(f) end;

procedure print;{打印} var

f ：text; begin

assign(f,fn2); rewrite(f);

writeln(f,total); writeln(f,max);

writeln(f,'(',x1,',',x2,')','(',x3,',',x4,')'); close(f) end;

procedure calc1;{计算房间数即每个方块所属的房间} var

i,j,k,x,y ：integer; open,closed ：integer; begin

fillchar(b,sizeof(b),0);{置所有方块未检查标志}

fillchar(area,sizeof(area),0);{所有房间的面积初始化为0} total：=0; i：=1; j：=0; repeat

inc(total);

repeat{搜索未确定房间的方块（I，j）} inc(j); if j>m then begin

j：=1; inc(i) end

until (i>n)or(b[i,j]=0);

if i>n then exit;{若所有方块都已检查则退出} fillchar(list,sizeof(list),0); list[1,1]：=i; list[1,2]：=j; b[i,j]：=total; area[total]：=1; open：=0; closed：=1; repeat

inc(open);

x：=list[open,1]; y：=list[open,2]; for k：=0 to 3 do

if a[x,y,k] and (b[x+way[k,1],y+way[k,2]]=0) then begin

inc(closed); inc(area[total]); list[closed,1]：=x+way[k,1]; list[closed,2]：=y+way[k,2];

b[list[closed,1],list[closed,2]]：=total end

until open>=closed until false end;

procedure calc2;{计算最大房间所含的方块数，即拆除那一堵墙可得最大房间} var

i,j ：integer;

newmax ：integer;{拆除一堵墙后最大房间所含的方块数} procedure evaluate(k,l：integer);{计算、比较、赋值} begin

if (b[i,j]<>b[k,l])and(area[b[i,j]]+area[b[k,l]]>newmax) then begin

newmax：=area[b[i,j]]+area[b[k,l]];

x1：=i; x2：=j; x3：=k; x4：=l {若（i,j）方块（k,l）属于两不同房间且两个房间的面积和大于当前的最大面积，则记录下新的最大面积以及这两个方块的编号} end end; begin

dec(total); max：=0; newmax：=0; for i：=1 to total do

if area[i]>max then max：=area[i]; {计算最大房间的面积} for i：=1 to n-1 do

for j：=1 to m do evaluate(i+1,j); {判断拆除东西方向之间的墙} for i：=1 to n do

for j：=1 to m-1 do evaluate(i,j+1) {判断拆除南北方向之间的墙} end;

procedure main; begin calc1; calc2 end; begin init; main; print end.

此题也可用深度优先搜索，但由于数据规模比较大，搜索的深度最多可达到5000左右，肯定会造成堆栈溢出，所以不宜采用，这里不再阐述。感兴趣的读者可以思考深搜的算法。 ?

优化方法

广度优先搜索是另一类常用的搜索方法，从搜索方法自身的特点而言，广度优先搜索的效率是远高于深度优先搜索的，这是因为就一棵搜索树而言，解的分布情况是不知道的，深度优先搜索在某些时候就会出现困死在某一个不存在解的树枝当中不断搜索的情况，而广度优先搜索则不会出现这样一种情况，但是广度优先搜索存在着一个相当大的弊病，就是扩展的节点的个数是成几何级数膨胀的，很快就导致内存溢出的情况。为了避免这些情况的出现，这里介绍几种优化广度优先搜索的算法。根据算法的特点，把主要的优化方法分为搜索策略上的优化和状态存储中的优化两大类。 搜索策略上的优化

搜索策略上的优化，主要介绍A*算法和双向搜索。

所谓A*算法，又称之为启发式搜索，主要是在搜索的过程中，选择较好的方法来扩张节点。在广度优先搜索当中，扩张出来的节点与目标节点的接近程度是不相同的，当然希望拿那些与目标节点越接近的节点来进行扩张，查找这些节点的方法是：对每个节点设计一个估价函数：f(n)=d(n)+w(n)，d(n)表示该节点在搜索树中的深度，w(n)表示该节点与目标节点接近程度，称这个函数为启发函数。为了更好的解释这个估价函数，来看一个例题。