網站首頁 編程語言 正文
分支限界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被遍歷到就停止搜索。
原文鏈接：https://blog.csdn.net/weixin_45816954/article/details/124949220
相關推薦
- 2022-05-21 Deployment副本無狀態服務創建及水平擴展_服務器其它
- 2022-10-06 react最流行的生態替代antdpro搭建輕量級后臺管理_React
- 2022-04-17 Security前后端分離自定義登錄詳解
- 2022-10-03 基于WPF實現控件輪廓跑馬燈動畫效果_C#教程
- 2022-07-13 IO流之字節流與常見編碼
- 2022-11-15 關于if?exists的用法及說明_MsSql
- 2022-12-22 C/C++?活動預處理器詳解_C 語言
- 2022-03-10 Android如何獲取APP啟動時間_Android
- 最近更新
-
- window11 系統安裝 yarn
- 超詳細win安裝深度學習環境2025年最新版（
- Linux 中運行的top命令 怎么退出？
- MySQL 中decimal 的用法？ 存儲小
- get 、set 、toString 方法的使
- @Resource和 @Autowired注解
- Java基礎操作-- 運算符，流程控制 Flo
- 1. Int 和Integer 的區別，Jav
- spring @retryable不生效的一種
- Spring Security之認證信息的處理
- Spring Security之認證過濾器
- Spring Security概述快速入門
- Spring Security之配置體系
- 【SpringBoot】SpringCache
- Spring Security之基于方法配置權
- redisson分布式鎖中waittime的設
- maven:解決release錯誤：Artif
- restTemplate使用總結
- Spring Security之安全異常處理
- MybatisPlus優雅實現加密？
- Spring ioc容器與Bean的生命周期。
- 【探索SpringCloud】服務發現-Nac
- Spring Security之基于HttpR
- Redis 底層數據結構-簡單動態字符串（SD
- arthas操作spring被代理目標對象命令
- Spring中的單例模式應用詳解
- 聊聊消息隊列，發送消息的4種方式
- bootspring第三方資源配置管理
- GIT同步修改后的遠程分支
提供CDN加速