Number of Islands

Given a boolean 2D matrix,0is represented as the sea,1is represented as the island. If two 1 is adjacent, we consider them in the same island. We only consider up/down/left/right adjacent. Find the number of islands.

Example:

Given graph:
[
  [1, 1, 0, 0, 0],
  [0, 1, 0, 0, 1],
  [0, 0, 0, 1, 1],
  [0, 0, 0, 0, 0],
  [0, 0, 0, 0, 1]
]
return 3.

Code:

public class Solution {
    /**
     * @param grid a boolean 2D matrix
     * @return an integer
     */
    public int numIslands(boolean[][] grid) {
        if (grid == null && grid.length == 0) {
            return 0;
        }
        int count = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                if (grid[i][j]) {
                    bfsSetToFalse(grid, i, j);
                    count++;
                }
            }
        }
        return count;
    }

    private void bfsSetToFalse(boolean[][] grid, int i, int j) {
        Queue<Integer> q = new LinkedList<>();
        int m = grid[0].length;
        q.offer(i * m + j);
        while (!q.isEmpty()) {
            int x = q.poll();
            int row = x / m;
            int col = x % m;
            setToFalse(grid, row - 1, col, q);
            setToFalse(grid, row + 1, col, q);
            setToFalse(grid, row, col - 1, q);
            setToFalse(grid, row, col + 1, q);
        }

    }

    private void setToFalse(boolean[][] grid, int i, int j, Queue<Integer> q) {
        if (i < 0 || i >= grid.length || j < 0 || j >= grid[i].length) {
            return;
        }
        if (grid[i][j]) {
            grid[i][j] = false;
            q.offer(i * grid[i].length + j);
        }
    }
}

results matching ""

    No results matching ""