文章目錄
- 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;
}