Leetcode热题100-200 岛屿数量

1. 题目描述

200 岛屿数量

2. 代码实现

1. dfs算法

class Solution {
public:int numIslands(vector<vector<char>>& grid) {int m = grid.size(), n = grid[0].size();int res = 0;// 注意lambda函数本身是不支持递归的,需要捕获自身来实现递归调用// 使用 lambda 表达式实现 DFSauto dfs = [&](auto&& dfs, int x, int y) -> void {// 超出边界检查if (x < 0 || x >= m || y < 0 || y >= n)return;// 不为陆地或者已访问过if (grid[x][y] != '1')return;// 设置为已访问grid[x][y] = '0';// 向四个方向递归dfs(dfs, x - 1, y); // 上dfs(dfs, x + 1, y); // 下dfs(dfs, x, y - 1); // 左dfs(dfs, x, y + 1); // 右};for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (grid[i][j] == '1') {dfs(dfs, i, j);res += 1;}}}return res;}
};

2. bfs算法

class Solution {
public:// 定义方向向量：上下左右vector<pair<int, int>> dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};int numIslands(vector<vector<char>>& grid) {int m = grid.size(), n = grid[0].size();int res = 0;// 使用bfs遍历的方式来实现for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (grid[i][j] == '1') {queue<pair<int, int>> que;que.push({i, j});// 标记为已访问grid[i][j] = '0';while (!que.empty()) {auto [x, y] = que.front();que.pop();// 遍历四个方向for (const auto& [dx, dy] : dirs) {int new_x = x + dx;int new_y = y + dy;// 判断是否越界以及是否为陆地if (new_x >= 0 && new_x < m && new_y >= 0 &&new_y < n && grid[new_x][new_y] == '1') {que.push({new_x, new_y});grid[new_x][new_y] = '0';}}}res++;}}}return res;}
};