Given a 2d grid map of
'1's (land) and '0's (water), count 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:
11110 11010 11000 00000
Answer: 1
Example 2:
11000 11000 00100 00011
Answer: 3
Understand the problem:
This problem is an alternative view of connected components in a undirected graph. It could be easily solved by using either DFS or BFS.
DFS Solution (Java):
public class Solution {
public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0 || grid[0].length == 0) {
return 0;
}
int rows = grid.length;
int cols = grid[0].length;
boolean[][] visited = new boolean[rows][cols];
int result = 0;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (grid[i][j] == '1' && !visited[i][j]) {
result++;
numIslandsHelper(grid, visited, i, j, rows, cols);
}
}
}
return result;
}
private void numIslandsHelper(char[][] grid, boolean[][] visited, int i, int j, int numRows, int numCols) {
if (i < 0 || i >= numRows) {
return;
}
if (j < 0 || j >= numCols) {
return;
}
if (visited[i][j]) {
return;
}
// If water
if (grid[i][j] == '0') {
return;
}
// Mark the visted[i][j] = true
visited[i][j] = true;
// Go up, down, left and right
numIslandsHelper(grid, visited, i - 1, j, numRows, numCols);
numIslandsHelper(grid, visited, i + 1, j, numRows, numCols);
numIslandsHelper(grid, visited, i, j - 1, numRows, numCols);
numIslandsHelper(grid, visited, i, j + 1, numRows, numCols);
}
}
A BFS Solution:
public class Solution {
private Queue<Integer> queue = new LinkedList();
public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0 || grid[0].length == 0) {
return 0;
}
int rows = grid.length;
int cols = grid[0].length;
boolean[][] visited = new boolean[rows][cols];
int result = 0;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (grid[i][j] == '1' && !visited[i][j]) {
result++;
numIslandsHelper(grid, visited, i, j, rows, cols);
}
}
}
return result;
}
private void numIslandsHelper(char[][] grid, boolean[][] visited, int i, int j, int numRows, int numCols) {
fill(grid, visited, i, j, numRows, numCols);
while (!queue.isEmpty()) {
int cord = queue.poll();
int x = cord / numCols;
int y = cord % numCols;
fill(grid, visited, x - 1, y, numRows, numCols);
fill(grid, visited, x + 1, y, numRows, numCols);
fill(grid, visited, x, y - 1, numRows, numCols);
fill(grid, visited, x, y + 1, numRows, numCols);
}
}
private void fill(char[][] grid, boolean[][] visited, int i, int j, int numRows, int numCols) {
if (i < 0 || i >= numRows || j < 0 || j >= numCols) {
return;
}
if (visited[i][j] || grid[i][j] == '0') {
return;
}
visited[i][j] = true;
queue.offer(i * numCols + j);
}
}
Update on 1/25/16:
Union-find Solution:
public class Solution {
private int[][] dir = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0) {
return 0;
}
int m = grid.length;
int n = grid[0].length;
int[] parents = new int[m * n];
int count = 0;
// Step 1: initialize each node, for each's parent is itself
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
int id = i * n + j;
parents[id] = id;
}
}
// step 2: iterate each node, and connect the neighbors
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == '0') {
continue;
}
for (int[] row : dir) {
int x = i + row[0];
int y = j + row[1];
if (isValid(grid, x, y)) {
int p = i * n + j;
int q = x * n + y;
connect(parents, p, q);
}
}
}
}
// step 3: count the number of cc
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
int id = i * n + j;
if (grid[i][j] == '1' && parents[id] == id) {
count++;
}
}
}
return count;
}
private boolean isValid(char[][] grid, int x, int y) {
int m = grid.length;
int n = grid[0].length;
return x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == '1';
}
private void connect(int[] parents, int p, int q) {
int pRoot = find(parents, p);
int qRoot = find(parents, q);
if (pRoot == qRoot) {
return;
}
parents[pRoot] = qRoot;
}
private int find(int[] parents, int id) {
while (parents[id] != id) {
id = parents[id];
}
return id;
}
}
Updata on 4/21/19:
public class Solution {
/**
* @param grid: a boolean 2D matrix
* @return: an integer
*/
public int numIslands(boolean[][] grid) {
// write your code here
if (grid == null || grid.length == 0) {
return 0;
}
int nRows = grid.length;
int nCols = grid[0].length;
int[] parents = new int[nRows * nCols];
for (int i = 0; i < parents.length; i++) {
parents[i] = i;
}
for (int i = 0; i < nRows; i++) {
for (int j = 0; j < nCols; j++) {
if (grid[i][j]) {
union(grid, i, j, parents);
}
}
}
int numIslands = 0;
for (int i = 0; i < parents.length; i++) {
int nx = i / nCols;
int ny = i % nCols;
if (grid[nx][ny] && parents[i] == i) {
numIslands++;
}
}
return numIslands;
}
private void union(boolean[][] grid, int x, int y, int[] parents) {
int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
int nRows = grid.length;
int nCols = grid[0].length;
for (int i = 0; i < 4; i++) {
int nx = x + dirs[i][0];
int ny = y + dirs[i][1];
if (nx >= 0 && nx < nRows && ny >= 0 && ny < nCols && grid[nx][ny]) {
int myParrent = find(parents, x * nCols + y);
int neighborParrent = find(parents, nx * nCols + ny);
if (myParrent != neighborParrent) {
parents[myParrent] = neighborParrent;
}
}
}
}
private int find(int[] parents, int x) {
int root = x;
while (parents[root] != root) {
root = parents[root];
}
// path compression
//
while (x != root) {
int temp = parents[x];
parents[x] = root;
x = temp;
}
return root;
}
}
No comments:
Post a Comment