99. 島嶼數量(深搜)
(1)題目描述:
(2)解題思路:
#include <iostream>
#include <vector>
using namespace std;int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1}; // 四個方向
void dfs(const vector<vector<int>>& grid, vector<vector<bool>>& visited, int x, int y) {for (int i = 0; i < 4; i++) {int nextx = x + dir[i][0];int nexty = y + dir[i][1];if (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue; // 越界了，直接跳過if (!visited[nextx][nexty] && grid[nextx][nexty] == 1) { // 沒有訪問過的 同時 是陸地的visited[nextx][nexty] = true;dfs(grid, visited, nextx, nexty);}}
}int main() {int n, m;cin >> n >> m;vector<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>> visited(n, vector<bool>(m, false));int result = 0;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (!visited[i][j] && grid[i][j] == 1) {visited[i][j] = true;result++; // 遇到沒訪問過的陸地，+1dfs(grid, visited, i, j); // 將與其鏈接的陸地都標記上 true}}}cout << result << endl;
}
(3)總結:
1.主要是深搜的過程如何將相鄰的節點都標記為訪問過的節點
2.這里終止條件就是dfs的if條件中相鄰的是陸地并且要是沒有訪問過的陸地（訪問過的陸地不可重復訪問）
99. 島嶼數量(廣搜)
(1)題目描述:
(2)解題思路:
#include <iostream>
#include <vector>
#include <queue>
using namespace std;int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1}; // 四個方向
void bfs(const vector<vector<int>>& grid, vector<vector<bool>>& visited, int x, int y) {queue<pair<int, int>> que;que.push({x, y});visited[x][y] = true; // 只要加入隊列，立刻標記while(!que.empty()) {pair<int ,int> cur = que.front(); que.pop();int curx = cur.first;int cury = cur.second;for (int i = 0; i < 4; i++) {int nextx = curx + dir[i][0];int nexty = cury + dir[i][1];if (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue; // 越界了，直接跳過if (!visited[nextx][nexty] && grid[nextx][nexty] == 1) {que.push({nextx, nexty});visited[nextx][nexty] = true; // 只要加入隊列立刻標記}}}
}int main() {int n, m;cin >> n >> m;vector<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>> visited(n, vector<bool>(m, false));int result = 0;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (!visited[i][j] && grid[i][j] == 1) {result++; // 遇到沒訪問過的陸地，+1bfs(grid, visited, i, j); // 將與其鏈接的陸地都標記上 true}}}cout << result << endl;
}
(3)總結:
1、每座島嶼只能由水平方向和/或豎直方向上相鄰的陸地連接形成。
2、遇到一個沒有遍歷過的節點陸地，計數器就加一，然后把該節點陸地所能遍歷到的陸地都標記上。在遇到標記過的陸地節點和海洋節點的時候直接跳過。 這樣計數器就是最終島嶼的數量。
3、加入隊列就代表走過，就需要標記
100. 島嶼的最大面積
(1)題目描述:
(2)解題思路:
// 版本一
#include <iostream>
#include <vector>
using namespace std;
int count;
int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1}; // 四個方向
void dfs(vector<vector<int>>& grid, vector<vector<bool>>& visited, int x, int y) {for (int i = 0; i < 4; i++) {int nextx = x + dir[i][0];int nexty = y + dir[i][1];if (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue; // 越界了，直接跳過if (!visited[nextx][nexty] && grid[nextx][nexty] == 1) { // 沒有訪問過的 同時 是陸地的visited[nextx][nexty] = true;count++;dfs(grid, visited, nextx, nexty);}}
}int main() {int n, m;cin >> n >> m;vector<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>> visited(n, vector<bool>(m, false));int result = 0;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (!visited[i][j] && grid[i][j] == 1) {count = 1; // 因為dfs處理下一個節點，所以這里遇到陸地了就先計數，dfs處理接下來的相鄰陸地visited[i][j] = true;dfs(grid, visited, i, j); // 將與其鏈接的陸地都標記上 trueresult = max(result, count);}}}cout << result << endl;}
(3)總結:
1.上一題的變形，此時計數器統計的是每一個島嶼中1的個數，因此需要放置在dfs中計數
