C++分支限界法实战：封闭区域填充、电梯调度与最短路径算法详解

基础应用：封闭区域识别与填充

第1步：识别并填充单组封闭区域

目的：解决在一个由 0 和 1 组成的 n x n 方阵中，找出被 1 完全包围的内部 0，并将其替换为 2 的问题。

入口与思路：直接定位内部封闭区域较难，采用逆向思维——所有不封闭的区域必然与矩阵的最外围边界相连。因此，从矩阵的边缘出发进行 BFS 搜索，所有能访问到的 0 都是非封闭区域，将其标记后，剩余未被访问的 0 即为需要填充的目标区域。

C++ 操作代码：

#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];
            // 检查是否越界、是否为边界(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; // 边界如果是1，则视为不可通达
        }
    }
    // 从第一行开始横向扫描
    for (int j = 1; j <= n;j++) {
        if (!vis[1][j]) bfs(1, j);
    }
    // 从最后一行开始横向扫描
    for (int j = 1; j <= n;j++) {
        if (!vis[n][j]) bfs(n, j);
    }
    // 从最左边一列纵向扫描
    for (int i = 2;i < n;i++) {
        if (!vis[i][1]) bfs(i, 1);
    }
    // 从最右边一列纵向扫描
    for (int i = 2;i < n;i++) {
        if (!vis[i][n]) bfs(i, n);
    }

    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 << " "; // 封闭区域内的0输出为2
        }
        cout << endl;
    }
    return 0;
}

第2步：寻找最大封闭区域并填充

目的：当存在多个封闭区域时，仅将面积最大的那个封闭区域内的 0 填充为 2。

入口与思路：首先需要彻底排除外部连通的影响。通过在数组外围虚构一圈 0 并对此区域执行 DFS 染色，可以确保任何与外部连通的 0 都被标记。随后在有效区域内对所有未访问的 0 进行遍历计数，保留面积最大的一组坐标标记。

C++ 操作代码：

#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' << ' '; // 仅最大封闭区输出2
			}
		}
		cout << endl;
	}
}

void dfs(int x, int y){
	// 越界或目标点不是0则返回
	if (a[x][y] != 0 || x < 0 || x > n + 1 || y < 0 || y > n + 1) { 
		return;
	}
	a[x][y] = id;
	cnt++;
	for (int 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];
	
	// 1. 先给最外圈多出的0进行初始染色，消除外部影响
	dfs(0, 0);
	id++;
	
	// 2. 在有效范围内(从第2层到倒数第2层)寻找封闭区域
	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++; 
		}
	}
	prit();
	return 0;
}

进阶应用：状态空间搜索与最短路径

第3步：解决电梯按钮最短调度问题

目的：在每层楼有固定升降规则（上 Ki 层或下 Ki 层）的电梯系统中，计算从 A 层到达 B 层的最少按键次数。

入口与思路：这是一个典型的无权图最短路径问题。每一层楼作为图的节点，可达的下一层楼作为边。使用 BFS 进行搜索，首次到达 B 层时的搜索深度即为最少按键数。

C++ 操作代码：

#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;
}

第4步：求解网格图中的最短通行距离

目的：在一个包含障碍（-1）和空地（0）的二维地图上，求出从起点到终点的最短步数，并输出带有距离标识的网格状态。

入口与思路：采用标准的层次 BFS。关键在于利用队列特性区分不同“轮次”。在循环开始前保存当前层的节点数量 s，逐层向外扩展。每当结束一轮处理，计数器 num 加 1。这样既记录了每个点的步数，也便于最后统一输出符合特定格式的结果。

C++ 操作代码：

#include<bits/stdc++.h>
using namespace std;
int Map[21][21] = { 0 }; // 记录区域信息
int m, n;
queue <int > q; 
int num = 1; // 记录当前是第几轮搜索（即步数）

void bfs(int sx, int sy, int ex, int ey) {
	int dir[4][2] = { {-1,0},{1,0},{0,-1},{0,1} }; 
	q.push(sx); q.push(sy);
	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++; // 完成一层，层数+1
	}
}
int main() {
	int sx, sy, ex, ey;
	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);
	
	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) // 与终点同层到达的点
				cout << "  0";
			else if (Map[i][j] < num) // 走过的路，显示步数
				printf("%3d", Map[i][j]);
		}
		cout << endl;
	}
	return 0;
}

总结

通过上述四个实验，我们可以看出分支限界法在 C++ 中的实现高度依赖队列结构和边界控制。无论是矩阵边界向外探测、状态树逐层扩展，还是网格坐标位移，掌握正确的入队出队逻辑与终止条件是实现高效算法的关键。以上就是C++分支限界法在算法题目中具体应用的详细内容，更多关于C++ 算法设计的资料请关注本站其它相关文章！