题解 | #岛屿数量#dfs

#include <bits/stdc++.h>
using namespace std;

class Solution {
  public:
    // 定义深度优先搜索函数
    void dfs(vector<vector<char>>& grid, int i, int j, int n, int m) {
        // 判断边界条件，以及当前位置是否为海洋   （'0'表示海洋）
        if (i < 0 || i >= n || j < 0 || j >= m || grid[i][j] == '0')
            return; // 如果超出边界或者当前位置为海洋，则直接返回

        // 将当前位置标记为已访问过的海洋，即将其值置为'0'
        grid[i][j] = '0';
        // 分别向上下左右四个方向进行递归搜索
        dfs(grid, i + 1, j, n, m); // 向下搜索
        dfs(grid, i, j + 1, n, m); // 向右搜索
        dfs(grid, i - 1, j, n, m); // 向上搜索
        dfs(grid, i, j - 1, n, m); // 向左搜索
    }
    // 主函数，求解岛屿数量
    int solve(vector<vector<char>>& grid) {
        int count = 0; // 记录岛屿数量
        int n = grid.size(); // 获取矩阵的行数
        int m = grid[0].size(); // 获取矩阵的列数
        // 定义方向数组，方便进行上下左右四个方向的遍历
        int dx[4] = {-1, 0, 1, 0}; // 上、右、下、左
        int dy[4] = {0, 1, 0, -1}; // 上、右、下、左
        // 遍历整个矩阵
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) 
            {
                if (grid[i][j] != '0') // 如果当前位置是陆地 （'1'表示陆地）
                { 
                    count++; // 岛屿数量加一
                    //对于每个陆地，进行深度优先搜索，将与该陆地相连的所有陆地标记为已访问
                    dfs(grid, i, j, n, m);
                }
            }
        }
        return count; // 返回岛屿数量
    }
};