Description
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
Credits:
Special thanks to @mithmatt for adding this problem and creating all test cases.
Solution
DFS, time O(m * n), space worst case O(m * n)
Space complexity : worst case O(M×N) in case that the grid map is filled with lands where DFS goes by M×N deep.
class Solution {
public static final int[][] DIRECTIONS = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
public int numIslands(char[][] grid) {
int islands = 0;
for (int i = 0; i < grid.length; ++i) {
for (int j = 0; j < grid[0].length; ++j) {
if (dfsExpand(grid, i, j)) {
++islands;
}
}
}
return islands;
}
public boolean dfsExpand(char[][] grid, int i, int j) {
if (!isValid(grid, i, j) || grid[i][j] != '1') {
return false;
}
grid[i][j] = '2'; // mark as visited
for (int[] direction : DIRECTIONS) {
dfsExpand(grid, i + direction[0], j + direction[1]);
}
return true;
}
public boolean isValid(char[][] grid, int i, int j) {
return i >= 0 && i < grid.length && j >= 0 && j < grid[0].length;
}
}
BFS, time O(m * n), space worst case O(min(M, N))
Space complexity : O(min(M,N)) because in worst case where the grid is filled with lands, the size of queue can grow up to min(M,N).
class Solution {
public static final int[][] DIRECTIONS = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
public int numIslands(char[][] grid) {
int islands = 0;
for (int i = 0; i < grid.length; ++i) {
for (int j = 0; j < grid[0].length; ++j) {
if (bfsExpand(grid, i, j)) {
++islands;
}
}
}
return islands;
}
public boolean bfsExpand(char[][] grid, int i, int j) {
if (!isValid(grid, i, j) || grid[i][j] != '1') {
return false;
}
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[] {i, j});
grid[i][j] = '2'; // mark as visited
while (!queue.isEmpty()) {
int[] pos = queue.poll();
for (int[] direction : DIRECTIONS) {
int x = pos[0] + direction[0];
int y = pos[1] + direction[1];
if (isValid(grid, x, y) && grid[x][y] == '1') {
queue.offer(new int[] {x, y});
grid[x][y] = '2';
}
}
}
return true;
}
public boolean isValid(char[][] grid, int i, int j) {
return i >= 0 && i < grid.length && j >= 0 && j < grid[0].length;
}
}
Union-find, time O(m * n), space O(m * n)
定义一个UnionFind class，里面的count成员表示由'1'组成的set的个数，初始化为grid中'1'的数量。然后遍历grid，分别向右和向下做union find，如果成功则count--，最终count即为所求。
注意这里扩张方向上的选择，由于在上面的dfs算法中，每次扩张都需要竭尽全力够到最广最深的地方，所以需要向上下左右四个方向扩展；但是在union-find算法中，只需要保证每个节点都被union-find过即可，所以只需向右和向下扩张就可以了。
class Solution {
public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0 || grid[0].length == 0) {
return 0;
}
int m = grid.length;
int n = grid[0].length;
UnionFind unionFind = new UnionFind(grid);
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] == '0') {
continue;
}
// try union find
if (i < m - 1 && grid[i + 1][j] != '0') {
unionFind.union(i * n + j, (i + 1) * n + j);
}
if (j < n - 1 && grid[i][j + 1] != '0') {
unionFind.union(i * n + j, i * n + j + 1);
}
}
}
return unionFind.count;
}
class UnionFind {
int count; // set of 1s count
int[] parent;
public UnionFind(char[][] grid) {
for (char[] row : grid) {
for (char c : row) {
if (c != '0') {
++count;
}
}
}
parent = new int[grid.length * grid[0].length];
Arrays.fill(parent, -1);
}
public int find(int i) {
if (parent[i] == -1) {
return i;
}
parent[i] = find(parent[i]);
return parent[i];
}
public void union(int i, int j) {
int iset = find(i);
int jset = find(j);
if (iset == jset) {
return;
}
parent[iset] = jset;
--count;
}
}
}
或者这样写：
class Solution {
public static final int[][] DIRECTIONS = {{1, 0}, {0, 1}};
public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0 || grid[0].length == 0) {
return 0;
}
int m = grid.length;
int n = grid[0].length;
int[] parent = new int[m * n];
for (int i = 0; i < parent.length; ++i) {
parent[i] = i;
}
int islands = m * n;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] != '1') {
--islands;
continue;
}
for (int[] direction : DIRECTIONS) {
int x = i + direction[0];
int y = j + direction[1];
if (isValid(grid, x, y) && grid[x][y] == '1') {
int iset = find(parent, getIndex(i, j, n));
int xset = find(parent, getIndex(x, y, n));
if (iset != xset) {
union(parent, iset, xset);
--islands;
}
}
}
}
}
return islands;
}
public int getIndex(int i, int j, int cols) {
return i * cols + j;
}
public int find(int[] parent, int x) {
if (parent[x] != x) {
parent[x] = find(parent, parent[x]);
}
return parent[x];
}
public void union(int[] parent, int xset, int yset) {
parent[xset] = parent[yset];
}
public boolean isValid(char[][] grid, int i, int j) {
return i >= 0 && i < grid.length && j >= 0 && j < grid[0].length;
}
}
