C++算法学习之分支限界法的应用
时间：2023-03-05 12:21:27 | 栏目：C代码 | 点击：次
分支限界1
实验题目： 填格子4
题目描述：
有一个由数字 0、1 组成的方阵中，存在一任意形状的封闭区域，封闭区域由数字1 包围构成，每个节点只能走上下左右 4 个方向。现要求把封闭区域内的所有空间都填写成2 .例如： 6×6 的方阵：
输入要求：
每组测试数据第一行一个整数 n(1≤n≤30)
接下来 n 行，由 0 和 1 组成的 n×n 的方阵。
封闭区域内至少有一个0
实验代码及注释:
#include<bits/stdc++.h>
using namespace std;
const int M = 31;
int Map[M][M]; // 记录输入格子的情况
bool vis[M][M] = { false }; // 标记格子访问情况，默认未访问
int n;
queue <int > q;
void bfs(int x, int y) { //广度优先搜索格子
int dir[4][2] = { {-1,0},{1,0},{0,-1},{0,1} }; // 上下左右四个方向
vis[x][y] = true; //标记格子为访问过
q.push(x);q.push(y);
while (!q.empty()) {
int w = q.front();
q.pop();
int e = q.front();
q.pop();
for (int i = 0;i < 4;i++) { //遍历四个方向向外扩展一圈
int now_x = w + dir[i][0];
int now_y = e + dir[i][1];
//判断新格子是否合法
if (1 <= now_x && now_x <= n && 1 <= now_y && now_y <= n && Map[now_x][now_y] == 0 && !vis[now_x][now_y]) {
vis[now_x][now_y] = true;//标记格子为访问过
q.push(now_x);q.push(now_y);
}
}
}
}
int main()
{
cin >> n;
for (int i = 1;i <= n;i++) {
for (int j = 1;j <= n;j++) {
cin >> Map[i][j];
if (Map[i][j] == 1)
vis[i][j] = true;
}
}
for (int i = 1;i <= n;i = i + n - 1) {//从边缘两行开始遍历
for (int j = 1; j <= n;j++) {
if (vis[i][j])
continue;
bfs(i, j);
}
}
for (int i = 1;i <= n;i = i + n - 1) {//从边缘两列开始遍历
for (int j = 1;j <= n;j++) {
if (vis[j][i])
continue;
bfs(j, i);
}
}
for (int i = 1;i <= n;i++) {
for (int j = 1;j <= n;j++) {
if (vis[i][j]) // 属于非封闭区域
cout << Map[i][j] << " ";
else
cout << 2 << " ";
}
cout << endl;
}
return 0;
}
算法分析与知识点：
本题的要求是找出给定方阵中的封闭区域并将区域内的方格填为2。已知封闭区域是由一圈完整的1所围成的，所以只需要遍历找到1和边界所围成的0并加以标记，最后只需要将方阵中未标记的方格输出为2就好了。
本题采用广度优先的搜索策略，每次以边界上的一个0为广度优先搜索的的起点，可以得知当遍历完边界上的0所有边界和1所围成的区域就都被标记了。
实验题目： 不如走楼梯
题目描述：
有个电梯，每一层楼都可以停，只是算法混乱了，所以你得写个补丁；第i层楼(1<=i<=N)上有一个数字Ki(0<=Ki<=N)，表示上或下的层数（相对于当前层），每层楼都可以上或下。当然，如果不能满足要求（没有的层），相应的按钮就会失灵。例如：3 3 1 2 5代表了Ki（在第一层可以上或下3层；当然下是不可能的，第三层可以上或下1层），从一楼开始。在一楼，按“上”可以到4楼，按“下”是不起作用的，因为没有-2楼。那么，从A楼到B楼至少要按几次按钮？
输入要求：
共二行。
第一行为3个用空格隔开的正整数，表示 N,A,B（共基层，开始层，结束层）；(1≤N≤200, 1≤A,B≤N)N,A,B(1≤N≤200,1≤A,B≤N)。
第二行为N个用空格隔开的非负整数，表示每层按钮的数值Ki。
输出要求：
一行，即最少按键次数；若无法到达，则输出?1。
实验代码及注释:
#include<bits/stdc++.h>
using namespace std;
int n, a, b, k[210];
bool f[210] = { false }; // 标记楼层是否访问过，默认没有
void bfs() {
queue<pair<int, int> > q; // 定义队列
pair<int, int> p, 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) { // 达到目标楼层
cout << p.second << endl;
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 << -1 << endl;
}
int main() {
cin >> n >> a >> b;
for (int i = 1; i <= n; i++)
cin >> k[i];
bfs(); //广度优先搜索答案
return 0;
}
算法分析与知识点：
本题要求在给定楼层和电梯按钮分布的前提下给出从初始楼层到目标楼层的最小按数。本题的路径搜索采用广度优先的搜索策略，只要搜索到目标楼层就停止搜索。最小的按电梯按钮数为此时搜索的深度。
分支限界 堂练
实验题目： 再填格子
题目描述：
有一个由数字 0、1 组成的方阵中，存在一任意形状的封闭区域，封闭区域由数字1 包围构成，每个节点只能走上下左右 4 个方向。现要求只把【最大封闭区域】内的空间填写成2 。
输入要求：
每组测试数据第一行一个整数 n(1≤n≤30)
接下来 n 行，由 0 和 1 组成的 n×n 的方阵。
封闭区域内至少有一个0，测试数据保证最大区域只有一个。
输出要求：
已经填好数字 2 的完整方阵。(每个数字后面有一个空格！）
实验代码及注释:
#include<bits/stdc++.h>
using namespace std;
int a[35][35] = { 0 }; // 记录方阵初始情况
int n;
int dir[4][2] = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} }; // 上下左右四个方向
int cnt = 0; //记录某一封闭区域的面积
int cnt_max = 0; // 记录最大封闭区域的面积
int id = 3; // 搜索标记
int id_max = id; // 最大封闭区域对应的搜索标记
void prit() { // 格式化输出函数
int i, j;
for (i = 1; i <= n; i++) {
for (j = 1; j <= n; j++) {
if (a[i][j] == 1) {
cout << a[i][j] << ' ';
}
else if (a[i][j] != id_max) {
cout << '0' << ' ';
}
else {
cout << '2' << ' ';
}
}
cout << endl;
}
}
void dfs(int x, int y)//将与其邻接的0坐标改为id
{
int i;
if (a[x][y] != 0 || x < 0 || x > n + 1 || y < 0 || y > n + 1) { //检查是否符合条件
return;
}
a[x][y] = id;
cnt++;
for (i = 0; i < 4; i++) { // 搜索四个方向
dfs(x + dir[i][0], y + dir[i][1]);
}
}
int main() {
int i, j;
cin >> n;
for (i = 1; i <= n; i++) { //输入方阵
for (j = 1; j <= n; j++) {
cin >> a[i][j];
}
}
//最外围的0不形成封闭区域
dfs(0, 0);
id++;
for (i = 2; i < n; i++) {//从第二层开始形成封闭区域
for (j = 2; j < n; j++) {
cnt = 0;
dfs(i, j);
if (cnt > cnt_max) { // 判断是否为最大封闭区域
cnt_max = cnt;
id_max = id;
}
id++; // 搜索标记+1
}
}
prit();
return 0;
}
算法分析与知识点：
首先在数组外面多围上一圈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之外，其他点无需标记。比如sample out只有b，没有9。
每个数值靠右占3位输出（含符号位），每行最后一个数值无空格换行。
详见sample output。（如无路径，按规则输出即可。）
实验代码及注释:
#include<bits/stdc++.h>
using namespace std;
int Map[21][21] = { 0 }; // 记录区域可通行情况
int m, n;
queue <int > q;
int num = 1; // 记录当前是第几轮搜索
void bfs(int x, int y, int ex, int ey) {
int dir[4][2] = { {-1,0},{1,0},{0,-1},{0,1} }; // 上下左右四个方向
q.push(x);q.push(y);
while (!q.empty()) {
int s = q.size() / 2; // 当前搜索轮次有几个点
for (int k = 0;k < s;k++) {
int cur_x = q.front();
q.pop();
int cur_y = q.front();
q.pop();
for (int i = 0;i < 4;i++) { // 遍历搜索四个方向
int now_x = cur_x + dir[i][0];
int now_y = cur_y + dir[i][1];
if (now_x == ex && now_y == ey) // 判断是否到终点
return;
if (0 <= now_x && now_x < n && 0 <= now_y && now_y < m && Map[now_x][now_y] == 0) { // 判断当前点是否符合条件
q.push(now_x);q.push(now_y);
Map[now_x][now_y] = num; // 标记当前点的搜索轮次
}
}
}
num++;
}
}
int sx, sy, ex, ey; // 起点终点坐标
int main() {
cin >> m >> n;
cin >> sx >> sy >> ex >> ey;
for (int i = 0;i < m;i++)
for (int j = 0;j < n;j++)
cin >> Map[i][j];
bfs(sx, sy, ex, ey);//调用bfs函数求解
for (int i = 0;i < m;i++) {
for (int j = 0;j < n;j++) {
if (i == sx && j == sy) // 起点
cout << " a";
else if (i == ex && j == ey) //终点
cout << " b";
else if (Map[i][j] == num) //与b同层的点
cout << " 0";
else {// 其余点
if (Map[i][j] < num)
printf("%3d", Map[i][j]);
}
//cout << "(" << i << "," << j << ")" << endl;
}
cout << endl;
}
return 0;
}
算法分析与知识点：
这题的要求是在给定通行情况的地图上找到从起点a到终点b的最短路径，这题可采用广度优先的搜索策略来做，在向外拓展的时候将新节点的标记值设为上一节点的标记值+1，只要终点b被搜索到就停止搜索，此时的搜索轮次就是从起点a到终点b的最短路径。
或者可以直接采用层次遍历的方法做，同样是终点b被遍历到就停止搜索。