Number of Islands
Given a boolean 2D matrix,0
is represented as the sea,1
is 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);
}
}
}