溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這篇文章主要講解了“C++分支限界法怎么應用”，文中的講解內容簡單清晰，易于學習與理解，下面請大家跟著小編的思路慢慢深入，一起來研究和學習“C++分支限界法怎么應用”吧！
題目描述：
有一個由數字 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++分支限界法怎么應用這一問題有了更深刻的體會，具體使用情況還需要大家實踐驗證。這里是億速云，小編將為大家推送更多相關知識點的文章，歡迎關注！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
