LeetCode 200. 岛屿数量（Java）

1. 岛屿数量

给定一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。

示例 1:

输入:

11110

11010

11000

00000

输出: 1

示例 2:

输入:

11000

11000

00100

00011

输出: 3

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/number-of-islands

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

判断方式：只要连在一起的岛屿就都算一个

方法一：广度优先搜索BFS

class Solution {
//
    class Point{
        int x;
        int y;
        public  Point(int x,int y)
        {
            this.x=x;
            this.y=y;
        }
    }
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length < 1) {
            return 0;
        }
        int count = 0;
        int len1 = grid.length;
        int[] moveX = {-1, 1, 0, 0};
        int[] moveY = {0, 0, -1, 1};
        //创建队列
        LinkedList<Point> queue = new LinkedList();
        for (int i = 0; i < len1 ; i++) 
        {
            int len2 = grid[i].length;
             for (int j = 0; j < len2; j++) 
             {
                 if (grid[i][j] == '1') {//如果为岛屿
                    count++;
                    grid[i][j] = '0';
                    queue.add(new Point(i, j));//则加入队列
                    // 广度优先遍历，上下左右染色
                     while (queue.size() != 0)  //如果队列不为空
                     {
                         Point p = queue.poll();//从队中取一个元素
                         //取其上下左右的元素进行判断
                         for (int k = 0; k < moveX.length; k++) 
                         {
                             int x = p.x + moveX[k];
                             int y = p.y + moveY[k];
                             if (isValid(len1, len2, x, y) && grid[x][y] == '1') //如果新节点没有越界且为1
                             {
                                 grid[x][y] = '0';//将遍历过的设为0
                                 queue.add(new Point(x, y));//并将新节点添加到队列中
                             }
                         }
                     }
                 }
             }
        }
        return count;
    }
    //判断是否越界
    private boolean isValid(int len1,int len2, int x, int y) {
        return x >= 0 && x < len1 && y >= 0 && y < len2;
    }
}
           

方法二：DFS深度优先搜索，递归查询

class Solution {
    public int numIslands(char[][] grid) {
        if(grid==null||grid.length==0)
        {
            return 0;
        }
        int len1=grid.length;
        int len2=grid[0].length;
        int count=0;
        for(int i=0;i<len1;i++)
        {
            for(int j=0;j<len2;j++)
            {
                if(grid[i][j]=='1')
                {
                    count++;
                    DFS(grid,i,j);
                }
            }
        }
        return count;
    }
    public void DFS(char[][] grid,int a,int b)
    {
        int len1=grid.length;
        int len2=grid[0].length;
        if(a<0||b<0||a>=len1||b>=len2||grid[a][b]=='0')
        {
            return;
        }
        grid[a][b]='0';
        DFS(grid,a-1,b);
        DFS(grid,a+1,b);
        DFS(grid,a,b-1);
        DFS(grid,a,b+1);
    }
}