200. 岛屿数量

---

题目链接

https://leetcode.cn/problems/number-of-islands/description/

代码实现

class Solution {
    public static int[][] dir = { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };

    public int numIslands(char[][] grid) {
        // n 行 m 列
        int n = grid.length;
        int m = grid[0].length;
        boolean[][] visited = new boolean[n][m];

        // 统计岛屿数量
        int cnt = 0;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                // 遇到 '1' 就把相连的节点都标记，说明是一片岛屿
                // 之后的循环再次遇到 '1'，则说明是一片新的岛屿
                if (!visited[i][j] && grid[i][j] == '1') {
                    // 优先处理该节点
                    visited[i][j] = true;
                    cnt++;
                    dfs(grid, i, j, visited);
                }
            }
        }

        return cnt;
    }

    // dfs 的作用是如果遇到 '1'，则会把与 '1' 相连的所有节点标记
    public void dfs(char[][] grid, int x, int y, boolean[][] visited) {
        for (int i = 0; i < dir.length; i++) {
            int nextX = x + dir[i][0];
            int nextY = y + dir[i][1];

            // 检查越界
            if (nextX < 0 || nextX >= grid.length || nextY < 0 || nextY >= grid[0].length) {
                continue;
            }

            if (!visited[nextX][nextY] && grid[nextX][nextY] == '1') {
                visited[nextX][nextY] = true;
                dfs(grid, nextX, nextY, visited);
            }
        }
    }
}