代码随想录算法训练营第五十天|99.岛屿数量、100.岛屿的最大面积

题目链接：99.岛屿数量

解题思路：深度优先搜索

具体思路：

首先定义上下左右四个方向的数组 dir，用于 dfs 时遍历相邻位置，读取矩阵的行数 n 和列数 m，构建二维数组 grid 并输入每个位置的数值，初始化与矩阵大小一致的访问标记数组 visited 初始全为 false 和岛屿计数 ans 初始为 0，双层循环遍历网格的每个位置，若该位置未被访问且为陆地，则判定为新岛屿，ans 加 1 并标记该位置为已访问，调用 dfs 函数遍历该岛屿的所有相邻陆地，dfs 函数接收 grid 数组、访问数组和当前位置，遍历四个方向计算下一个位置，先判断是否越界，越界则跳过，若下一个位置未被访问且为陆地，标记为已访问并递归调用 dfs，直至该岛屿的所有陆地都被标记为已访问，最终输出 ans 即为网格中的岛屿总数。

具体代码：

#include<iostream> #include<vector> using namespace std; int dir[4][2] = {{1, 0}, {0, 1}, {-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; dfs(grid, visited, nextx, nexty); } } } int main () { int n; int 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]; } } int ans = 0; vector<vector<bool>> visited(n, vector<bool>(m, false)); 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; ans++; dfs(grid, visited, i, j); } } } cout << ans << endl; }

解题思路：广度优先搜索

具体思路：

首先定义上下左右四个方向的数组 dir，用于 bfs 时遍历当前位置的相邻位置，读取矩阵的行数 n 和列数 m，构建二维数组 grid 并输入每个位置的数值，初始化与矩阵大小一致的访问标记数组 visited 初始全为 false 和岛屿计数 ans 初始为 0，双层循环遍历网格的每个位置，若该位置未被访问且为陆地，则判定为新岛屿，ans 加 1 并标记该位置为已访问，调用 bfs 函数遍历该岛屿的所有相邻陆地，bfs 函数接收 grid 数组、访问数组和初始陆地位置 (x, y)，先初始化队列并将 (x, y) 入队，然后循环取出队首节点 (curx, cury)，遍历四个方向计算相邻位置，先判断相邻位置是否越界，越界则跳过，若相邻位置未被访问且为陆地，则标记该位置为已访问并将其入队，直至队列为空，即该岛屿的所有陆地均被标记，最终输出 ans 即为网格中的岛屿总数。

具体代码：

#include<iostream> #include<vector> #include<queue> using namespace std; int dir[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}}; void bfs(vector<vector<int>>& grid, vector<vector<bool>>& visited, int x, int y) { queue<pair<int, int>> queue; queue.push({x, y}); while(!queue.empty()) { pair<int, int> cur = queue.front(); queue.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) { queue.push({nextx, nexty}); visited[nextx][nexty] = true; } } } } int main () { int n; int 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]; } } int ans = 0; vector<vector<bool>> visited(n, vector<bool>(m, false)); 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; ans++; bfs(grid, visited, i, j); } } } cout << ans << endl; }

题目链接：100.岛屿的最大面积

解题思路：深度优先搜索

具体思路：

首先定义上下左右四个方向的数组 dir，用于 dfs 遍历当前位置的相邻陆地，声明全局变量 area 记录当前岛屿的面积，读取矩阵的行数 n 和列数 m，构建二维数组 grid 并输入每个位置的数值，初始化与矩阵大小一致的访问标记数组 visited 初始全为 false 和全局最大面积 ans 初始为 0，通过双层循环遍历网格的每个位置，若该位置未被访问且为陆地，则将当前岛屿面积 area 初始化为 1计入当前这块陆地，标记该位置为已访问，调用 dfs 函数遍历该岛屿的所有相邻陆地，dfs 函数接收 grid 数组、访问数组和当前位置，遍历四个方向计算相邻位置，先判断是否越界，越界则跳过，若相邻位置未被访问且为陆地，标记该位置为已访问、将 area 加 1 并递归调用 dfs，每完成一个岛屿的 dfs 遍历后，用当前岛屿的面积 area 更新全局最大面积 ans ，取 ans 和 area 的最大值，最终输出 ans 即为网格中最大的岛屿面积。

具体代码：

#include<iostream> #include<vector> using namespace std; int dir[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}}; int area; 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; area++; dfs(grid, visited, nextx, nexty); } } } int main() { int n; int 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]; } } int ans = 0; vector<vector<bool>> visited(n, vector<bool>(m, false)); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (!visited[i][j] && grid[i][j] == 1) { area = 1; visited[i][j] = true; dfs(grid, visited, i, j); ans = max(area, ans); } } } cout << ans << endl; }

解题思路：广度优先搜索

具体思路：

首先定义上下左右四个方向的数组 dir，用于 bfs 遍历当前位置的相邻陆地，声明全局变量 area 记录当前岛屿的面积，读取矩阵的行数 n 和列数 m，构建二维数组 grid 并输入每个位置的数值，初始化与矩阵大小一致的访问标记数组 visited 初始全为 false 和全局最大面积 ans 初始为 0，通过双层循环遍历网格的每个位置，若该位置未被访问且为陆地，则将当前岛屿面积 area 初始化为 1，计入当前这块陆地，标记该位置为已访问，调用 bfs 函数遍历该岛屿的所有相邻陆地，bfs 函数接收 grid 数组、访问数组和初始陆地位置 (x, y)，先初始化队列并将 (x, y) 入队，然后循环取出队首节点 (curx, cury)，遍历四个方向计算相邻位置，先判断相邻位置是否越界，越界则跳过，若相邻位置未被访问且为陆地，标记该位置为已访问、将 area 加 1 并将该位置入队，直至队列为空，即该岛屿的所有陆地均被遍历，每完成一个岛屿的 bfs 遍历后，用当前岛屿的面积 area 更新全局最大面积 ans，取 ans 和 area 的最大值，最终输出 ans 即为网格中最大的岛屿面积。

具体代码：

#include<iostream> #include<vector> #include<queue> using namespace std; int dir[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}}; int area; void bfs(vector<vector<int>>& grid, vector<vector<bool>>& visited, int x, int y) { queue<pair<int, int>> queue; queue.push({x, y}); while(!queue.empty()) { pair<int, int> cur = queue.front(); queue.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) { visited[nextx][nexty] = true; area++; queue.push({nextx, nexty}); } } } } int main() { int n; int 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]; } } int ans = 0; vector<vector<bool>> visited(n, vector<bool>(m, false)); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (!visited[i][j] && grid[i][j] == 1) { area = 1; visited[i][j] = true; bfs(grid, visited, i, j); ans = max(area, ans); } } } cout << ans << endl; }