题目描述

给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。

题目分析

深度优先搜索。使用数组 visited 标记被访问过的点。
遍历grid，值为 1 且没有被访问过，则认为是新岛屿，调用 DFS 对岛屿内的所有陆地做标记。

Java

boolean[][] visited;
char[][] grid;
int m, n;

public int numIslands(char[][] grid) {
    this.grid = grid;
    m = grid.length;
    n = grid[0].length;
    int count = 0;
    visited = new boolean[m][n];
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == '1' && !visited[i][j]) {
                count++;
                dfs(i, j);
            }
        }
    }
    return count;
}

private void dfs(int i, int j) {
    if (i < 0 || i >= m || j < 0 || j >= n || visited[i][j] || grid[i][j] != '1') {
        return;
    }
    visited[i][j] = true;
    dfs(i, j + 1);
    dfs(i, j - 1);
    dfs(i + 1, j);
    dfs(i - 1, j);
}

Kotlin

private lateinit var grid: Array<CharArray>
private lateinit var visited: Array<BooleanArray>

fun numIslands(grid: Array<CharArray>): Int {
    this.grid = grid
    visited = Array(grid.size) { BooleanArray(grid[0].size) }
    var count = 0
    for (i in grid.indices) {
        for (j in grid[0].indices) {
            if (grid[i][j] == '1' && !visited[i][j]) {
                dfs(i, j)
                count++
            }
        }
    }
    return count
}

private fun dfs(i: Int, j: Int) {
    if (i !in grid.indices || j !in grid[0].indices || visited[i][j] || grid[i][j] != '1') {
        return
    }
    visited[i][j] = true
    dfs(i, j + 1)
    dfs(i, j - 1)
    dfs(i - 1, j)
    dfs(i + 1, j)
}