算法设计与分析---回溯+分支限界法实验报告

《算法设计与分析》作业

作业四+五回溯法+分支限界法

1. 二元最大连通块搜索

因为下了场大雨，青蛙王子高兴坏了，它有机会重新划定自己的王国范围。在下图中，空白区域表示积水的地方，青蛙王子需要找到一块最大的连续积水区域（上下或左右相连）作为自己的新领地。

2. 三元最大连通块搜索

小明在玩一种消除游戏。游戏中有一个长方形的区域，被RGB(红绿蓝)三种颜色的小球充满。要求每次找出当前最大连通区域（上下左右相邻同种颜色即可算作连通），进行消除。

####.###

###.####

##.#####

the ans is 7

12 8

..#.....

.##....#

.#....#.

.###.#..

....#...

..##.#..

.#....#.

.##..#.#

###..#..

....#...

...#....

..#.....

the ans is 18

1.3 程序运行情况

1.4 程序源码（含注释）

#include"bits/stdc++.h"

using namespace std;

#define inf 999

//代码下标从0始，输入时.为可走，#为不可走

int n,m;//行、列

int ans,now;//最大连通数，当前搜索时连通数

char e[inf][inf];//地图

int book[inf][inf];//标记地图

int pos[4][2]={-1,0,1,0,0,1,0,-1};//方位，上下右左

void read()//输入数据

{

printf("input the row and the column of the map:"); scanf("%d%d",&n,&m);

printf("now input the map:\n");

for(int i=0;i

scanf("%s",e[i]);

2.4 程序源码（含注释）

#include"bits/stdc++.h"

using namespace std;

#define inf 999

//代码下标从0始

int n,m;//行、列

int ans,now;//最大连通数，当前搜索时连通数

int ans_x,ans_y;//最大连通对应的字符

char e[inf][inf];//地图

int book[inf][inf];//标记地图

int pos[4][2]={-1,0,1,0,0,1,0,-1};//方位，上下右左

void read()//输入数据

{

printf("input the row and the column of the map:");

scanf("%d%d",&n,&m);

printf("now input the map:\n");

for(int i=0;i

scanf("%s",e[i]);