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被遍歷到就停止搜索。
到此這篇關於C++算法學習之分支限界法的應用的文章就介紹到這瞭,更多相關C++ 分支限界法內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！