本文共 1387 字，大约阅读时间需要 4 分钟。

一、问题描述

给定一个二维数组，其元素均为'1'和'0'，分别代表陆地和水，现在要计算数组中岛屿的数量。

被水包围的就是岛屿，此外，数组的四条边界均被水包围。

PS：某司的校招机试也出了这道题，该题反过来求一块有水有陆地的地域中湖泊的数量，解法完全一样。

测试用例：

Input: grid = [  ["1","1","1","1","0"],  ["1","1","0","1","0"],  ["1","1","0","0","0"],  ["0","0","0","0","0"]]Output: 1Input: grid = [  ["1","1","0","0","0"],  ["1","1","0","0","0"],  ["0","0","1","0","0"],  ["0","0","0","1","1"]]Output: 3

二、代码实现

总体思路是进行两层for循环遍历二维数组的所有元素，对于每个遍历到的元素，如果是'1'，将其置为'0'，并且将它上下左右相邻的S也置为'0'； 如果是'0'，直接continue跳过该元素。

class Solution {    public int numIslands(char[][] grid) {        if (grid == null || grid.length == 0) {            return 0;        }                int res = 0;    // 计数器（岛屿的数量）        for (int i=0; i < grid.length; i++) {            for (int j=0; j < grid[0].length; j++) {                if (grid[i][j] == '1') {                    dfs(i, j, grid);                    res ++;                }            }        }        return res;    }    private void dfs(int i, int j, char[][] grid) {        grid[i][j] = '0';        if (i-1 >= 0 && grid[i-1][j] == '1') {  // 上            dfs(i-1, j, grid);        }        if (i+1 < grid.length && grid[i+1][j] == '1') { // 下            dfs(i+1, j, grid);        }        if (j-1 >= 0 && grid[i][j-1] == '1') {  // 左            dfs(i, j-1, grid);        }        if (j+1 < grid[0].length && grid[i][j+1] == '1') { // 右            dfs(i, j+1, grid);        }    } }

转载地址：http://tfnii.baihongyu.com/