代碼隨想錄day52圖論3

文章目錄

  • 101. 孤島的總面積
  • 102. 沉沒孤島
  • 103. 水流問題
  • 104.建造最大島嶼

101. 孤島的總面積

題目鏈接
文章講解

#include<bits/stdc++.h>
using namespace std;int ans = 0;       // 記錄不與邊界相連的孤島數量
int sum = 0;       // 當前孤島的面積
bool flag = false; // 標記當前孤島是否與邊界相連
// 方向數組:右,下,左,上
int direct[4][2] = {0, 1, 1, 0, -1, 0, 0, -1};// 廣度優先搜索(BFS)函數,用于遍歷連通區域
void bfs(vector<vector<int>>& grid, vector<vector<bool>>& visit, int x, int y)
{queue<pair<int, int>> q;q.push({x, y});visit[x][y] = true;while(!q.empty()){pair<int, int> cur = q.front();q.pop();int curx = cur.first;int cury = cur.second;// 遍歷四個方向for(int i = 0; i < 4; i++){int nextx = curx + direct[i][0];int nexty = cury + direct[i][1];// 如果下一個位置越界,跳過if(nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue;// 如果該位置是陸地且未訪問過if(grid[nextx][nexty] == 1 && !visit[nextx][nexty]){q.push({nextx, nexty});  // 將新的位置加入隊列visit[nextx][nexty] = true;  // 標記該位置為已訪問sum++;  // 當前孤島的面積加一// 如果當前孤島接觸到邊界,則設置標記為 trueif(nextx == 0 || nextx == grid.size() - 1 || nexty == 0 || nexty == grid[0].size() - 1)flag = true;}}}
}int main(){int n, m;cin >> n >> m;  // 輸入網格的行數和列數// 初始化網格和訪問標記數組vector<vector<int>> grid(n, vector<int>(m, 0));  // 網格,0表示水域,1表示陸地vector<vector<bool>> visit(n, vector<bool>(m, false));  // 訪問標記數組,初始為未訪問// 輸入網格的數據for(int i = 0; i < n; i++){for(int j = 0; j < m; j++){cin >> grid[i][j];  // 輸入每個位置的值}}// 遍歷網格內部的區域(排除邊界區域)for(int i = 1; i < n - 1; i++)  // 遍歷行,從第2行到倒數第2行{for(int j = 1; j < m - 1; j++)  // 遍歷列,從第2列到倒數第2列{// 如果當前位置是陸地且未訪問過,啟動 BFS 遍歷該連通區域if(!visit[i][j] && grid[i][j] == 1){sum = 1;  // 當前孤島的面積從1開始(包括當前位置)flag = false;  // 初始化標記,假設該孤島不與邊界相連bfs(grid, visit, i, j);  // 執行 BFS,遍歷孤島// 如果該孤島沒有接觸到邊界,則將其計入最終結果if(!flag) ans += sum;}}}// 輸出最終結果:不與邊界相連的孤島總面積cout << ans;
}

102. 沉沒孤島

題目鏈接
文章講解

#include<bits/stdc++.h>
using namespace std;bool flag;  // 標記當前島嶼是否與邊界相連
int direct[4][2] = {0, 1, 1, 0, -1, 0, 0, -1};  // 方向數組:右、下、左、上// BFS 用于遍歷并判斷孤島是否與邊界相連
void bfs(vector<vector<int>>& grid, vector<vector<bool>>& visit, int x, int y)
{queue<pair<int, int>> q;q.push({x, y});visit[x][y] = true;// 如果島嶼接觸到邊界,標記為與邊界相連if(x == 0 || x == grid.size() - 1 || y == 0 || y == grid[0].size() - 1)flag = true;// 開始 BFS 遍歷while(!q.empty()){pair<int, int> cur = q.front();q.pop();int curx = cur.first;int cury = cur.second;// 遍歷四個方向for(int i = 0; i < 4; i++){int nextx = curx + direct[i][0];int nexty = cury + direct[i][1];// 如果下一個位置越界,跳過if(nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue;// 如果是陸地且未訪問過if(grid[nextx][nexty] == 1 && !visit[nextx][nexty]){q.push({nextx, nexty});visit[nextx][nexty] = true;// 如果接觸到邊界,將 flag 設置為 trueif(nextx == 0 || nextx == grid.size() - 1 || nexty == 0 || nexty == grid[0].size() - 1)flag = true;}}}
}// BFS2 用于將不與邊界相連的島嶼沉沒
void bfs2(vector<vector<int>>& grid, vector<vector<bool>>& visit, int x, int y)
{queue<pair<int, int>> q;q.push({x, y});visit[x][y] = true;grid[x][y] = 0;  // 沉沒該島嶼部分// 開始 BFS 沉沒孤島while(!q.empty()){pair<int, int> cur = q.front();q.pop();int curx = cur.first;int cury = cur.second;// 遍歷四個方向for(int i = 0; i < 4; i++){int nextx = curx + direct[i][0];int nexty = cury + direct[i][1];// 如果下一個位置越界,跳過if(nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue;// 如果是陸地且未訪問if(grid[nextx][nexty] == 1){q.push({nextx, nexty});visit[nextx][nexty] = true;grid[nextx][nexty] = 0;  // 沉沒該島嶼部分}}}
}int main(){int n, m;cin >> n >> m;  // 輸入網格的行數和列數vector<vector<int>> grid(n, vector<int>(m, 0));  // 網格初始化,默認都是水域(0)vector<vector<bool>> visit(n, vector<bool>(m, false));  // 訪問標記數組// 輸入網格數據,1 表示陸地,0 表示水域for(int i = 0; i < n; i++){for(int j = 0; j < m; j++){cin >> grid[i][j];}}// 遍歷網格中的所有陸地for(int i = 0; i < n; i++){for(int j = 0; j < m; j++){// 對每個未訪問過的陸地執行 BFSif(!visit[i][j] && grid[i][j] == 1)  {flag = false;  // 假設當前孤島不與邊界相連bfs(grid, visit, i, j);  // 執行 BFS,檢查該島嶼是否與邊界相連if(!flag)  // 如果孤島不與邊界相連,則將其沉沒{bfs2(grid, visit, i, j);}}}}// 輸出沉沒后的網格for(int i = 0; i < n; i++){for(int j = 0; j < m; j++){cout << grid[i][j];if(j == m - 1) cout << endl;  // 每行末尾換行else cout << " ";  // 每個元素間加空格}}return 0;
}

103. 水流問題

題目鏈接
文章講解

#include<bits/stdc++.h>
using namespace std;// 方向數組:右,下,左,上
int direct[4][2] = {0, 1, 1, 0, -1, 0, 0, -1};// BFS 用于遍歷網格,找到所有符合條件的點
void bfs(vector<vector<int>>& grid, vector<vector<bool>>& visit, int x, int y) {queue<pair<int, int>> q;q.push({x, y});visit[x][y] = true;while (!q.empty()) {auto cur = q.front();q.pop();int curx = cur.first;int cury = cur.second;// 遍歷四個方向for (int i = 0; i < 4; i++) {int nextx = curx + direct[i][0];int nexty = cury + direct[i][1];// 邊界檢查if (nextx < 0 || nexty < 0 || nextx >= grid.size() || nexty >= grid[0].size())continue;// 如果滿足條件且未訪問過if (grid[nextx][nexty] >= grid[curx][cury] && !visit[nextx][nexty]) {q.push({nextx, nexty});visit[nextx][nexty] = true;}}}
}int main() {int n, m;cin >> n >> m;// 初始化 grid,二維矩陣,初值為 0vector<vector<int>> grid(n, vector<int>(m, 0));// 輸入矩陣數據for (int i = 0; i < n; i++)for (int j = 0; j < m; j++)cin >> grid[i][j];// 用于存儲從邊界流出的區域vector<vector<bool>> lb(n, vector<bool>(m, false));vector<vector<bool>> rb(n, vector<bool>(m, false));// 從上邊界和下邊界出發進行 BFSfor (int i = 0; i < m; i++) {bfs(grid, lb, 0, i);    // 從上邊界bfs(grid, rb, n - 1, i); // 從下邊界}// 從左邊界和右邊界出發進行 BFSfor (int i = 0; i < n; i++) {bfs(grid, lb, i, 0);    // 從左邊界bfs(grid, rb, i, m - 1); // 從右邊界}// 輸出可以同時從第一組和第二組邊界流出的坐標for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (lb[i][j] && rb[i][j]) {cout << i << " " << j << endl;}}}return 0;
}

104.建造最大島嶼

題目鏈接
文章講解
先遍歷所有的陸地塊 1,用 BFS 把每個島嶼標記為不同的編號(從 2 開始),并記錄每個島嶼的面積。

遍歷所有的水塊 0,嘗試將其變成 1,并計算其上下左右 4 個方向連接的不同島嶼編號的面積和,得到變換后的最大面積。

特判:如果原始矩陣全是陸地,則直接返回 n * m。

#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <queue>
using namespace std;int n, m;
int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1}; // 右 下 左 上// BFS 標記島嶼 & 計算面積
int bfs(vector<vector<int>>& grid, vector<vector<bool>>& visited, int x, int y, int mark) {int area = 0;queue<pair<int, int>> q;q.push({x, y});visited[x][y] = true;grid[x][y] = mark;while (!q.empty()) {auto [cx, cy] = q.front(); q.pop();area++;for (int i = 0; i < 4; i++) {int nx = cx + dir[i][0];int ny = cy + dir[i][1];if (nx >= 0 && nx < n && ny >= 0 && ny < m &&!visited[nx][ny] && grid[nx][ny] == 1) {q.push({nx, ny});visited[nx][ny] = true;grid[nx][ny] = mark;}}}return area;
}int main() {cin >> n >> m;vector<vector<int>> grid(n, vector<int>(m));for (int i = 0; i < n; ++i)for (int j = 0; j < m; ++j)cin >> grid[i][j];vector<vector<bool>> visited(n, vector<bool>(m, false));unordered_map<int, int> area_map; // mark -> areaint mark = 2; // 島嶼編號從2開始// Step 1: 標記島嶼編號并統計面積for (int i = 0; i < n; ++i) {for (int j = 0; j < m; ++j) {if (!visited[i][j] && grid[i][j] == 1) {int area = bfs(grid, visited, i, j, mark);area_map[mark] = area;mark++;}}}// Step 2: 嘗試將每個水塊變為陸地,記錄最大面積int max_area = 0;bool all_land = true;for (int i = 0; i < n; ++i) {for (int j = 0; j < m; ++j) {if (grid[i][j] == 0) {all_land = false;unordered_set<int> seen; // 記錄周圍不同的島嶼int total = 1; // 當前水變陸地后的初始面積為1for (int d = 0; d < 4; ++d) {int ni = i + dir[d][0];int nj = j + dir[d][1];if (ni >= 0 && ni < n && nj >= 0 && nj < m) {int neighbor_mark = grid[ni][nj];if (neighbor_mark > 1 && !seen.count(neighbor_mark)) {total += area_map[neighbor_mark];seen.insert(neighbor_mark);}}}max_area = max(max_area, total);}}}// 如果全是陸地,沒有任何水塊if (all_land) {cout << n * m << endl;} else {cout << max_area << endl;}return 0;
}

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/diannao/93984.shtml
繁體地址,請注明出處:http://hk.pswp.cn/diannao/93984.shtml
英文地址,請注明出處:http://en.pswp.cn/diannao/93984.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

linux pip/conda 修改默認cache位置

1 pip pip cache默認在/home/{username}目錄下&#xff0c;容易導致系統盤寫滿報錯。查看pip cache位置pip cache dir假設移動pip cache目錄到 /data/.cache/pip/cache&#xff0c;命令如下pip config set global.cache-dir /data/.cache/pip/cache2 conda 查看conda緩存位置c…

如何解決pip安裝報錯ModuleNotFoundError: No module named ‘seaborn’問題

【Python系列Bug修復PyCharm控制臺pip install報錯】如何解決pip安裝報錯ModuleNotFoundError: No module named ‘seaborn’問題 一、摘要 在使用 PyCharm 終端進行模塊安裝時&#xff0c;常常會遇到如下異常&#xff1a; ModuleNotFoundError: No module named ‘seaborn’…

(思維)洛谷 P13551 ももいろの鍵 題解

題意 愛莉給了你一個非負整數 nnn&#xff0c;你需要把 0,1,2,…,n0, 1, 2, \dots, n0,1,2,…,n 劃分成若干組&#xff0c;滿足每一組的按位與為 000。 劃分的組不需要相鄰。 你需要最大化劃分組數并給出方案。 1≤T≤6001 \le T \le 6001≤T≤600&#xff0c;0≤n≤1050 \le n…

記錄一次ESP32報錯Guru Meditation Error: Core 1 panic‘ed (Double exception).

一、問題描述 需求&#xff1a; ESP32S3單片機&#xff0c;連接一個麥克風讀取5s后&#xff0c;編碼后發送到百度云進行語音識別。通過freertos框架&#xff0c;將任務放在核1中運行&#xff08;放在核0同樣報錯&#xff09; 問題&#xff1a; 在最后的發送語音數據中&#xff…

半導體物理復習

半導體物理導論第一章 半導體的電子狀態

vi/vim跳轉到指定行命令

在 vi/vim 中跳轉到指定行有多種高效方法&#xff0c;以下是最常用的操作方式&#xff1a; 一、基礎跳轉&#xff1a;行號 命令命令模式下直接輸入行號 按 Esc 切換到命令模式后&#xff0c;輸入 :行號 并回車。例如&#xff0c;輸入 :100 會直接跳轉到第 100 行。使用 G 快捷…

智能落地扇方案:青稞RISC-V電機 MCU一覽

在科技飛速發展的今天&#xff0c;智能家居已成為人們生活中不可或缺的一部分&#xff0c;而風扇作為夏日解暑的必備家電&#xff0c;其智能化升級也成為了行業發展的必然趨勢。傳統落地扇功能單一、操作不便&#xff0c;已難以滿足現代消費者對便捷、舒適、節能生活的追求。在…

SQL 中 WHERE 與 HAVING 的用法詳解:分組聚合場景下的混用指南

SQL中WHERE與HAVING的用法詳解&#xff1a;分組聚合場景下的混用指南 1. WHERE與HAVING的基本區別 在SQL查詢中&#xff0c;WHERE和HAVING都是用于過濾數據的子句&#xff0c;但它們的應用時機和作用對象有本質區別&#xff1a; WHERE子句&#xff1a;在分組前對原始數據進行過…

14 - 大語言模型 — 抽取式問答系統 “成長記”:靠 BERT 學本事,從文本里精準 “揪” 答案的全過程(呆瓜版-1號)

目錄 1、什么是問答系統&#xff1f; 2、問答系統的核心工作流程 2.1、理解問題&#xff1a;把問題 “翻譯” 成機器能懂的形式 2.2、 尋找答案&#xff1a;從信息中定位答案 2.3、生成答案&#xff1a;整理并輸出結果 2.4、優化迭代&#xff1a;讓系統更 “聰明” 3、主…

Docker一鍵部署輕量級Gitea倉庫

1、安裝docker 1、安裝依賴包 yum install -y yum-utils device-mapper-persistent-data lvm22、配置docker yum源 yum-config-manager --add-repo http://mirrors.aliyun.com/docker-ce/linux/centos/docker-ce.repo3、安裝docker yum install -y docker-ce4、修改docker配置文…

2025年滲透測試面試題總結-2025年HW(護網面試) 81(題目+回答)

安全領域各種資源&#xff0c;學習文檔&#xff0c;以及工具分享、前沿信息分享、POC、EXP分享。不定期分享各種好玩的項目及好用的工具&#xff0c;歡迎關注。 目錄 2025年HW(護網面試) 81 一、Webshell獲取路徑規劃 二、變形注入突破技巧 三、MySQL寫入Webshell條件矩陣 …

8.1IO進程線程——文件IO函數

文章目錄一、思維導圖二、使用文件IO函數&#xff0c;實現文件的拷貝myhead.h代碼現象三、使用標準IO函數&#xff0c;實現圖片的拷貝代碼現象四、使用文件IO函數&#xff0c;計算文件的大小代碼現象五、牛客網刷題一、思維導圖 二、使用文件IO函數&#xff0c;實現文件的拷貝 …

xerces-c-src_2_8_0 arm_linux編譯

xerces-c-src_2_8_0 ARM LINUX 編譯 文章借鑒&#xff1a;https://bbs.csdn.net/topics/250017321 export XERCESCROOT/xxxx/xerces-c-src_2_8_0 1 下載地址https://archive.apache.org/dist/xerces/c/sources/xerces-c-src_2_8_0.tar.gz&#xff1a;xerces-c-src_2_8_0.tar…

20250729使用WPS打開xlsx格式的電子表格時候隱藏顯示fx的編輯欄的方法

20250729使用WPS打開xlsx格式的電子表格時候隱藏顯示fx的編輯欄的方法 2025/7/29 9:44緣起&#xff1a;視圖→編輯欄 截屏的時候&#xff0c;顯示fx的編輯欄 占用空間了&#xff0c;很討厭。 想辦法拿掉&#xff01;

springboot當中ConfigurationProperties注解作用跟數據庫存入有啥區別

在Spring Boot中&#xff0c;ConfigurationProperties注解用于將外部配置文件&#xff08;如application.properties或application.yml&#xff09;中的屬性映射到Java對象中。這種方式使得配置管理更加靈活和集中。而將配置信息存入數據庫則是另一種管理應用程序配置的方式。這…

JVM指針壓縮的那些事

什么是指針壓縮&#xff1f;指針壓縮&#xff08;Compressed Ordinary Object Pointers&#xff0c;簡稱Compressed OOPs&#xff09;是JVM在64位平臺上的一種內存優化技術&#xff0c;它將64位的對象引用壓縮為32位&#xff0c;從而減少內存占用并提升性能。為什么需要指針壓縮…

【數據結構初階】--排序(一):直接插入排序,希爾排序

&#x1f525;個人主頁&#xff1a;草莓熊Lotso &#x1f3ac;作者簡介&#xff1a;C研發方向學習者 &#x1f4d6;個人專欄&#xff1a; 《C語言》 《數據結構與算法》《C語言刷題集》《Leetcode刷題指南》 ??人生格言&#xff1a;生活是默默的堅持&#xff0c;毅力是永久的…

Hive SQL (HQL) 編輯指南

Hive SQL&#xff08;HQL&#xff09;是基于Hive的數據倉庫查詢語言&#xff0c;語法類似標準SQL&#xff0c;但因Hive的離線大數據處理特性&#xff0c;存在一些特有規則和最佳實踐。以下是Hive SQL的編輯指南&#xff0c;涵蓋核心語法、注意事項和優化技巧&#xff1a; 一、H…

力扣熱題100--------240.搜索二維矩陣

編寫一個高效的算法來搜索 m x n 矩陣 matrix 中的一個目標值 target 。該矩陣具有以下特性&#xff1a; 每行的元素從左到右升序排列。 每列的元素從上到下升序排列。 示例 1&#xff1a;輸入&#xff1a;matrix [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24…

【pytest高階】-2- 內置hook插件擴展機制和定制開發

一、可愛版 pytest 插件 & hook 知識大禮包 &#x1f381;準備好和 pytest 插件來一場可愛約會了嗎&#xff5e; 咱們用超甜的 emoji 把知識串成棉花糖&#x1f361; 一口一個知識點&#xff01;一、 pytest 插件&#xff1a;框架的 “魔法百寶箱” &#x1f9d9;?♀?1. …