By

前言

Github：https://github.com/HealerJean

博客：http://blog.healerjean.com

1、岛屿数量

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

示例 1:

输入:11110
    11010
    11000
    00000
输出: 1

示例 2:

输入:
    11000
    11000
    00100
    00011
输出: 3
    解释: 每座岛屿只能由水平和/或竖直方向上相邻的陆地连接而成。

1.1、解题思路

和求最大岛屿面积一样方法，一样，只不过这个是count

1.2、算法

public int numIslands(char[][] grid) {

        int count = 0 ;
        for (int i = 0 ; i < grid.length ; i++){
            for (int j = 0 ; j < grid[0].length ; j++){
                if (grid[i][j] == '1'){
                    //只要能进入就代表肯定可以
                    count ++ ;
                    kuosan(i, j, grid);
                }
            }
        }
        return count ;
    }

    public void kuosan(int i, int j, char[][] grid) {
        if (i >= 0 && i < grid.length
                && j >= 0 && j < grid[0].length
                && grid[i][j] == '1') {

            //设为0，下次不进入了
            grid[i][j] = 0 ;
            kuosan(i-1 , j, grid);
            kuosan(i+1, j, grid);
            kuosan(i,j-1,grid);
            kuosan(i,j+1,grid);
        }
    }

1.3、测试

    @Test
    public void test() {
        char[][] matrix = {
                {'1', '1', '1', '1', '0'},
                {'1', '1', '0', '1', '0'},
                {'1', '1', '0', '0', '0'},
                {'0', '0', '0', '0', '0'}
        };

        System.out.println(numIslands(matrix));
    }

​

ContactAuthor