leetcode200. 岛屿数量

leetcode200. 岛屿数量

五月 23, 2020

leetcode200. 岛屿数量

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

示例 1:
输入:
11110
11010
11000
00000
输出: 1

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

思路

简单的dfs。
遍历所有的点，当遇到1的时候，说明是岛屿，开始dfs，并且标记，计数器加一。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
public int numIslands(char[][] grid) {
        if (grid.length == 0) return 0;
        int[][] direction = {{0,1}, {1,0}, {0,-1}, {-1,0}};
        int[][] visited = new int[grid.length][grid[0].length];//记录是否访问过
        int count = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
            //我看了很多评论和题解，基本都是遍历所有的点，没法优化
                if (visited[i][j] != 0) continue;//访问过的不能访问
                if (grid[i][j] == '0') {//为0不能访问
                    visited[i][j] = -1;
                    continue;
                }
                Queue<int[]> queue = new LinkedList<>();
                queue.offer(new int[]{i,j});
                visited[i][j] = 1;
                while (!queue.isEmpty()) {
                //发现当前是1了，开始bfs
                    int[] tmp = queue.poll();
                    int x = tmp[0], y = tmp[1];
                    for (int k = 0; k < 4; k++) {
                        int nextX = x + direction[k][0];
                        int nextY = y + direction[k][1];
                        if (nextX < 0 || nextY < 0 || nextX > grid.length - 1 || nextY > grid[0].length - 1) 
                        	continue;
                        if (grid[nextX][nextY] == '0') 
                            continue;
                        if (visited[nextX][nextY] == 1)
                            continue;
                        queue.offer(new int[]{nextX,nextY});
                        visited[nextX][nextY] = 1;
                    }
                }
                count++;
            }
        }
        
        return count;
    }

leetcode 83/100