200. Number of Islands[Medium]

200. Number of Islands

Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands.

An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Constraints:

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 300
• grid[i][j] is '0' or '1'.

Example

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

思路

题解

   public int numIslands(char[][] grid) {
        int row, col, res;
        res = 0;
        row = grid.length;
        col = grid[0].length;
        boolean[][] path = new boolean[row][col];

        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
		// 只有满足当前值为1，并且还没被标记过，开始广度遍历这个点，及其相连的点
                if (!path[i][j] && grid[i][j] == '1') {
                    bfsNumIsLands(i, j, grid, path);
		    // 广度遍历结束后，这块岛屿记录完成，结果+1
                    res++;
                }
            }
        }
        return res;
    }

    private void bfsNumIsLands(int row, int col, char[][] grid, boolean[][] path) {
	// 存储往四个方向移动到坐标
        int[][] directions = new int[][]{{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
	// 广度遍历用队列
        Queue<List<Integer>> curVisit = new LinkedList<>();
	// 已经做过坐标判断了，直接入队
        curVisit.add(Arrays.asList(row, col));
        while (!curVisit.isEmpty()) {
            List<Integer> cur = curVisit.poll();
	    // 四个方向走
            for (int[] dire : directions) {
                int newRow = cur.get(0) + dire[0];
                int newCol = cur.get(1) + dire[1];
                if (newRow < 0 || newRow >= grid.length || newCol < 0 || newCol >= grid[0].length ||
                        path[newRow][newCol] || grid[newRow][newCol] == '0')
                    continue;
                curVisit.add(Arrays.asList(newRow, newCol));
                path[newRow][newCol] = true;
            }
        }
    }