200. Number of Islands

Problem

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.

Example 1:

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

Example 2:

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

Constraints:

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

Solution

解這題的想法是，對每一個未訪問過的 land，用 DFS 或 BFS 去訪問相鄰 lands。當相鄰 cell 為 land 時，再繼續訪問其相鄰 lands，一直無法再擴張為止。這樣就得到一個 island。然後，再找下一個未訪問過的 land 做上述相同的動作，一直到所有的 land 都被訪問過。

DFS

• Time:
• Space:

class Solution {
    public int numIslands(char[][] grid) {
        boolean[][] visited = new boolean[grid.length][grid[0].length];
        int islands = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == '1' && !visited[i][j]) {
                    dfs(grid, i, j, visited);
                    islands++;
                }
            }
        }
        return islands;
    }

    private void dfs(char[][] grid, int i, int j, boolean[][] visited) {
        visited[i][j] = true;
        int[][] dirs = new int[][] {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        for (int[] dir : dirs) {
            int r = i + dir[0];
            int c = j + dir[1];
            if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length) continue;
            if (visited[r][c] || grid[r][c] == '0') continue;
            dfs(grid, r, c, visited);
        }
    }
}

BFS

• Time:
• Space:

class Solution {
    public int numIslands(char[][] grid) {
        boolean[][] visited = new boolean[grid.length][grid[0].length];
        int islands = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == '1' && !visited[i][j]) {
                    bfs(grid, i, j, visited);
                    islands++;
                }
            }
        }
        return islands;
    }

    private void bfs(char[][] grid, int row, int col, boolean[][] visited) {
        Queue<int[]> queue = new ArrayDeque<>();
        queue.offer(new int[] {row, col});
        int[][] dirs = new int[][] {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        while (!queue.isEmpty()) {
            int[] pos = queue.poll();
            if (visited[pos[0]][pos[1]]) continue;
            visited[pos[0]][pos[1]] = true;
            for (int[] dir : dirs) {
                int r = pos[0] + dir[0];
                int c = pos[1] + dir[1];
                if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length) continue;
                if (grid[r][c] == '0' || visited[r][c]) continue;
                queue.offer(new int[] {r, c});
            }
        }
    }
}

參考

• 200. Number of Islands, LeetCode.
• 200. Number of Islands, LeetCode Solutions.