「代码随想录算法训练营」第四十四天 | 图论 part2

200. 岛屿数量

题目链接:https://leetcode.cn/problems/number-of-islands/description/
文章讲解:https://programmercarl.com/kamacoder/0099.岛屿的数量深搜.html
题目难度:中等
题目状态:看题解

思路一:深搜版

方法 dfs

  • 参数: 接受一个字符网格 grid 和当前坐标 (r, c)
  • 功能: 将当前岛屿的所有相连部分标记为已访问。
  • 实现:
    • 改变当前坐标的值为 '0',表示已访问。
    • 检查上下左右四个方向,如果相邻位置是 '1',递归调用 dfs

方法 numIslands

  • 参数: 接受一个字符网格 grid
  • 功能: 计算网格中岛屿的数量。
  • 实现:
    • 获取网格的行数 nr 和列数 nc
    • 初始化岛屿计数器 num_islands 为 0。
    • 遍历网格中的每个元素,如果遇到 '1'
      • 增加岛屿计数器。
      • 调用 dfs 方法,从该位置开始将整个岛屿标记为已访问。
    • 返回岛屿的总数。

代码一:

class Solution {
public:
    void dfs(vector<vector<char>> &grid, int r, int c) {
        int nr = grid.size();
        int nc = grid[0].size();
        grid[r][c] = '0';
        if(r - 1 >= 0 && grid[r - 1][c] == '1') dfs(grid, r - 1, c);
        if(r + 1 < nr && grid[r + 1][c] == '1') dfs(grid, r + 1, c);
        if(c - 1 >= 0 && grid[r][c - 1] == '1') dfs(grid, r, c - 1);
        if(c + 1 < nc && grid[r][c + 1] == '1') dfs(grid, r, c + 1);
    }

    int numIslands(vector<vector<char>>& grid) {
        int nr = grid.size();
        if(!nr) return 0;
        int nc = grid[0].size();
        
        int num_islands = 0;
        for(int r = 0; r < nr; ++r) {
            for(int c = 0; c < nc; ++c) {
                if(grid[r][c] == '1') {
                    ++num_islands;
                    dfs(grid, r, c);
                }
            }
        }
        return num_islands;
    }
};

消耗一:

思路二:广搜版

思路在代码中。

代码二:

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        int rowCount = grid.size();
        int colCount = grid[0].size();
        // 用来记录岛屿数量
        int num_islands = 0;
        for (int row = 0; row < rowCount; row++) {
            for (int col = 0; col < colCount; col++) {
                // 如果当前点是岛屿的一部分
                if (grid[row][col] == '1') {
                    // 岛屿数量增加
                    num_islands++;
                    // 将当前位置标记为'0', 表示已访问
                    grid[row][col] = '0';
                    // 创建一个队列, 用于存储岛屿的所有相邻点
                    queue<pair<int, int>> neighbors; 
                    // 将当前位置加入队列
                    neighbors.emplace(row, col);
                    // 当队列不为空时,继续搜索
                    while (!neighbors.empty()) {
                        auto [row, col] = neighbors.front();
                        neighbors.pop();
                        // 检查并将当前点的上下左右四个相邻点加入队列(如果它们是未访问的岛屿部分)
                        if (row - 1 >= 0 && grid[row - 1][col] == '1') {
                            neighbors.emplace(row - 1, col);
                            grid[row - 1][col] = '0'; // 标记为已访问
                        }
                        if (row + 1 < rowCount && grid[row + 1][col] == '1') {
                            neighbors.emplace(row + 1, col);
                            grid[row + 1][col] = '0'; // 标记为已访问
                        }
                        if (col - 1 >= 0 && grid[row][col - 1] == '1') {
                            neighbors.emplace(row, col - 1);
                            grid[row][col - 1] = '0'; // 标记为已访问
                        }
                        if (col + 1 < colCount && grid[row][col + 1] == '1') {
                            neighbors.emplace(row, col + 1);
                            grid[row][col + 1] = '0'; // 标记为已访问
                        }
                    }
                }
            }
        }
        return num_islands;
    }
};

消耗二:

695. 岛屿的最大面积

题目链接:https://leetcode.cn/problems/max-area-of-island/description/
文章讲解:https://programmercarl.com/kamacoder/0100.岛屿的最大面积.html
题目难度:中等
题目状态:看题解

DFS解法

思路:

  • 方法 IslandDFS:这是一个递归方法,用于计算单个岛屿的面积。

    • 参数
      • grid:二维网格,表示地图。
      • ij:当前格子的行和列索引。
    • 逻辑
      • 检查当前索引是否在网格范围内。
      • 如果当前格子是水(值为0),返回0。
      • 如果是陆地(值为1),将其标记为0(已访问),然后递归地检查四个方向(上、下、左、右)的相邻格子。
      • 返回值为1(当前格子)加上所有相邻陆地格子的面积。
  • 方法 maxAreaOfIsland:计算网格中所有岛屿的最大面积。

    • 逻辑
      • 初始化最大面积 ans 为0。
      • 遍历网格的每个格子。
      • 对于每个陆地格子,调用 IslandDFS 计算该岛屿的面积,并更新最大面积。
      • 返回最大面积。

代码:

class Solution {
public:
    int IslandDFS(vector<vector<int>> &grid, int i, int j) {
        if((i < grid.size()) && (i >= 0) && (j < grid[0].size()) && (j >= 0)) {
            if(grid[i][j] == 0) return 0;
            else {
                grid[i][j] = 0;
                return 1 + IslandDFS(grid, i - 1, j) + IslandDFS(grid, i + 1, j) + IslandDFS(grid, i, j - 1) + IslandDFS(grid, i, j + 1);
            }
        } else 
            return 0;
    }

    int maxAreaOfIsland(vector<vector<int>>& grid) {
        int ans = 0;
        for(int i = 0; i < grid.size(); ++i) {
            for(int j = 0; j < grid[0].size(); ++j) {
                ans = max({ans, IslandDFS(grid, i, j)});
            }
        }
        return ans;
    }
};

消耗:

BFS解法

看不懂。。。

代码:

class Solution {
public:
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        int ans = 0;
        for (int i = 0; i != grid.size(); ++i) {
            for (int j = 0; j != grid[0].size(); ++j) {
                int cur = 0;
                queue<int> queuei;
                queue<int> queuej;
                queuei.push(i);
                queuej.push(j);
                while (!queuei.empty()) {
                    int cur_i = queuei.front(), cur_j = queuej.front();
                    queuei.pop();
                    queuej.pop();
                    if (cur_i < 0 || cur_j < 0 || cur_i == grid.size() || cur_j == grid[0].size() || grid[cur_i][cur_j] != 1) {
                        continue;
                    }
                    ++cur;
                    grid[cur_i][cur_j] = 0;
                    int di[4] = {0, 0, 1, -1};
                    int dj[4] = {1, -1, 0, 0};
                    for (int index = 0; index != 4; ++index) {
                        int next_i = cur_i + di[index], next_j = cur_j + dj[index];
                        queuei.push(next_i);
                        queuej.push(next_j);
                    }
                }
                ans = max(ans, cur);
            }
        }
        return ans;
    }
};