C++算法学习之分支限界法的应用

第C++算法学习之分支限界法的应用目录分支限界1实验题目：填格子4实验题目：不如走楼梯分支限界堂练实验题目：再填格子实验题目：最短路径

分支限界1

实验题目：填格子4

题目描述：

有一个由数字0、1组成的方阵中，存在一任意形状的封闭区域，封闭区域由数字1包围构成，每个节点只能走上下左右4个方向。现要求把封闭区域内的所有空间都填写成2.例如：66的方阵：

输入要求：

每组测试数据第一行一个整数n(1n30)

接下来n行，由0和1组成的nn的方阵。

封闭区域内至少有一个0

实验代码及注释:

#includebits/stdc++.h

usingnamespacestd;

constintM=31;

intMap[M][M];//记录输入格子的情况

boolvis[M][M]={false};//标记格子访问情况，默认未访问

intn;

queueint

voidbfs(intx,inty){//广度优先搜索格子

intdir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};//上下左右四个方向

vis[x][y]=true;//标记格子为访问过

q.push(x);q.push(y);

while(!q.empty()){

intw=q.front();

q.pop();

inte=q.front();

q.pop();

for(inti=0;ii++){//遍历四个方向向外扩展一圈

intnow_x=w+dir[i][0];

intnow_y=e+dir[i][1];

//判断新格子是否合法

if(1=now_xnow_x=n1=now_ynow_y=nMap[now_x][now_y]==0!vis[now_x][now_y]){

vis[now_x][now_y]=true;//标记格子为访问过

q.push(now_x);q.push(now_y);

intmain()

cinn;

for(inti=1;ii++){

for(intj=1;jj++){

cinMap[i][j];

if(Map[i][j]==1)

vis[i][j]=true;

for(inti=1;ii=i+n-1){//从边缘两行开始遍历

for(intj=1;jj++){

if(vis[i][j])

continue;

bfs(i,j);

for(inti=1;ii=i+n-1){//从边缘两列开始遍历

for(intj=1;jj++){

if(vis[j][i])

continue;

bfs(j,i);

for(inti=1;ii++){

for(intj=1;jj++){

if(vis[i][j])//属于非封闭区域

coutMap[i][j]"";

else

cout2"";

coutendl;

return0;

算法分析与知识点：

本题的要求是找出给定方阵中的封闭区域并将区域内的方格填为2。已知封闭区域是由一圈完整的1所围成的，所以只需要遍历找到1和边界所围成的0并加以标记，最后只需要将方阵中未标记的方格输出为2就好了。

本题采用广度优先的搜索策略，每次以边界上的一个0为广度优先搜索的的起点，可以得知当遍历完边界上的0所有边界和1所围成的区域就都被标记了。

实验题目：不如走楼梯

题目描述：

有个电梯，每一层楼都可以停，只是算法混乱了，所以你得写个补丁；第i层楼(1=i=N)上有一个数字Ki(0=Ki=N)，表示上或下的层数（相对于当前层），每层楼都可以上或下。当然，如果不能满足要求（没有的层），相应的按钮就会失灵。例如：33125代表了Ki（在第一层可以上或下3层；当然下是不可能的，第三层可以上或下1层），从一楼开始。在一楼，按上可以到4楼，按下是不起作用的，因为没有-2楼。那么，从A楼到B楼至少要按几次按钮？

输入要求：

共二行。

第一行为3个用空格隔开的正整数，表示N,A,B（共基层，开始层，结束层）；(1N200,1A,BN)N,A,B(1N200,1A,BN)。

第二行为N个用空格隔开的非负整数，表示每层按钮的数值Ki。

输出要求：

一行，即最少按键次数；若无法到达，则输出1。

实验代码及注释:

#includebits/stdc++.h

usingnamespacestd;

intn,a,b,k[210];

boolf[210]={false};//标记楼层是否访问过，默认没有

voidbfs(){

queuepairint,int//定义队列

pairint,intp,t;//当前第几层，当前按了几次

p.first=a;p.second=0;//赋初值

q.push(p);//进入队列

while(!q.empty()){//队列非空

p=q.front();q.pop();

if(f[p.first])//如果楼层访问过

continue;

f[p.first]=true;//标记楼层访问过

if(p.first==b){//达到目标楼层

coutp.secondendl;

return;//退出搜索

if(p.first-k[p.first]0){//向下按

t.first=p.first-k[p.first];

t.second=p.second+1;

q.push(t);

if(p.first+k[p.first]=n){//向上按

t.first=p.first+k[p.first];

t.second=p.second+1;

q.push(t);

cout-1endl;

intmain(){

cinnab;

for(inti=1;ii++)

cink[i];

bfs();//广度优先搜索答案

return0;

算法分析与知识点：

本题要求在给定楼层和电梯按钮分布的前提下给出从初始楼层到目标楼层的最小按数。本题的路径搜索采用广度优先的搜索策略，只要搜索到目标楼层就停止搜索。最小的按电梯按钮数为此时搜索的深度。

分支限界堂练

实验题目：再填格子

题目描述：

有一个由数字0、1组成的方阵中，存在一任意形状的封闭区域，封闭区域由数字1包围构成，每个节点只能走上下左右4个方向。现要求只把【最大封闭区域】内的空间填写成2。

输入要求：

每组测试数据第一行一个整数n(1n30)

接下来n行，由0和1组成的nn的方阵。

封闭区域内至少有一个0，测试数据保证最大区域只有一个。

输出要求：

已经填好数字2的完整方阵。(每个数字后面有一个空格！）

实验代码及注释:

#includebits/stdc++.h

usingnamespacestd;

inta[35][35]={0};//记录方阵初始情况

intn;

intdir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};//上下左右四个方向

intcnt=0;//记录某一封闭区域的面积

intcnt_max=0;//记录最大封闭区域的面积

intid=3;//搜索标记

intid_max=id;//最大封闭区域对应的搜索标记

voidprit(){//格式化输出函数

inti,j;

for(i=1;ii++){

for(j=1;jj++){

if(a[i][j]==1){

couta[i][j]'';

elseif(a[i][j]!=id_max){

cout'0''';

else{

cout'2''';

coutendl;

voiddfs(intx,inty)//将与其邻接的0坐标改为id

inti;

if(a[x][y]!=0||x0||xn+1||y0||yn+1){//检查是否符合条件

return;

a[x][y]=id;

cnt++;

for(i=0;ii++){//搜索四个方向

dfs(x+dir[i][0],y+dir[i][1]);

intmain(){

inti,j;

cinn;

for(i=1;ii++){//输入方阵

for(j=1;jj++){

cina[i][j];

//最外围的0不形成封闭区域

dfs(0,0);

id++;

for(i=2;ii++){//从第二层开始形成封闭区域

for(j=2;jj++){

cnt=0;

dfs(i,j);

if(cntcnt_max){//判断是否为最大封闭区域

cnt_max=cnt;

id_max=id;

id++;//搜索标记+1

prit();

return0;

算法分析与知识点：

首先在数组外面多围上一圈0，通过深搜将外层的0及其连接块染色染色后，剩下的0元素都为封闭区域，接下来找到最大的区域对每个元素都进行深搜，找到最大的区域，记录其染色编号。

实验题目：最短路径

题目描述：

在下图中，请使用广度搜索求出a到b的最短路径，有色区域为不可通过区域。

输入要求：

第1行2个整数，表示区域的行数m和列数n。1=m,n=20

第2行4个整数，表示起点坐标和终点坐标，坐标计数从0开始。

第3行开始，m行n列的区域数据，0表示可通行，-1表示不可通行（图中绿色部分）。

输出要求：

如图a的二维信息数据，数值表示步数。起点终点分别用字符a、b表示。

最后与b同层的点，除了b之外，其他点无需标记。比如sampleout只有b，没有9。

每个数值靠右占3位输出（含符号位），每行最后一个数值无空格换行。

详见sampleoutput。（如无路径，按规则输出即可。）

实验代码及注释:

#includebits/stdc++.h

usingnamespacestd;

intMap[21][21]={0};//记录区域可通行情况

intm,n;

queueint

intnum=1;//记录当前是第几轮搜索

voidbfs(intx,inty,intex,intey){

intdir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};//上下左右四个方向

q.push(x);q.push(y);

while(!q.empty()){

ints=q.size()/2;//当前搜索轮次有几个点

for(intk=0;kk++){

intcur_x=q.front();

q.pop();

intcur_y=q.front();

q.pop();

for(inti=0;ii++){//遍历搜索四个方向

intnow_x=cur_x+dir[i][0];

intnow_y=cur_y+dir[i][1];

if(now_x==exnow_y==ey)//判断是否到终点

return;

if(0=now_xnow_xn0=now_ynow_ymMap[now_x][now_y]==0){//判断当前点是否符合条件

q.push(now_x);q.push(now_y);

Map[now_x][now_y]=num;//标记当前点的搜索轮次

num++;

intsx,sy,ex,ey;//起点终点坐标

intmain()