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
Solution1：DFS, recursively
a最好在递归前就check是否visited，如果没有visit过，再递归去visit
b或是写法简单的：直接dfs，但每次进入递归再检查是否visited/出界
Time Complexity: O(nm) Space Complexity: O(nm) 递归缓存
Solution2：DFS, stack
在放入stack前就check是否visited，如果没有visit过，再放入stack
Time Complexity: O(nm) Space Complexity: O(nm)
Solution3：BFS, queue
在放入queue前就check是否visited，如果没有visit过，再放入queue
Time Complexity: O(nm) Space Complexity: O(nm)
Solution4：Union Find
将为'1'的每个元素初始id标为其序号，遍历并union邻域的'1'，最终种类数count就是land数量。之所以要传入grid判断是否为1再assign id是因为需要将最终种类数count==land数，不需要0 involved.
Time Complexity: O(NlogN)? Space Complexity: O(N) N=m*n
Solution1a Code：
class Solution {
public int numIslands(char[][] grid) {
int count = 0;
for(int row = 0; row < grid.length; row++) {
for(int col = 0; col < grid[0].length; col++) {
if(grid[row][col] == '1') {
dfs(grid, row, col);
count++;
}
}
}
return count;
}
private void dfs(char[][] grid, int row, int col) {
// if(row < 0 || col < 0 || row > grid.length - 1|| col > grid[0].length - 1) return;
// visited marked as 0
grid[row][col] = '0';
if(row > 0 && grid[row - 1][col] == '1') {
dfs(grid, row - 1, col);
}
if(row < grid.length - 1 && grid[row + 1][col] == '1') {
dfs(grid, row + 1, col);
}
if(col > 0 && grid[row][col - 1] == '1') {
dfs(grid, row, col - 1);
}
if(col < grid[0].length - 1 && grid[row][col + 1] == '1') {
dfs(grid, row, col + 1);
}
}
}
Solution1b Code：
class Solution {
public int numIslands(char[][] grid) {
int count = 0;
for(int row = 0; row < grid.length; row++) {
for(int col = 0; col < grid[0].length; col++) {
if(grid[row][col] == '1') {
dfs(grid, row, col);
count++;
}
}
}
return count;
}
private void dfs(char[][] grid, int row, int col) {
if (row < 0 || col < 0 || row > grid.length - 1 || col > grid[0].length - 1 || grid[row][col] != '1') return;
grid[row][col] = '0';
dfs(grid, row + 1, col);
dfs(grid, row - 1, col);
dfs(grid, row, col + 1);
dfs(grid, row, col - 1);
}
}
Solution2 Code：
class Solution {
public int numIslands(char[][] grid) {
int count = 0;
for(int row = 0; row < grid.length; row++) {
for(int col = 0; col < grid[0].length; col++) {
if(grid[row][col] == '1') {
dfs(grid, row, col);
count++;
}
}
}
return count;
}
private void dfs(char[][] grid, int row, int col) {
Deque<Integer> stack = new ArrayDeque<Integer>();
int n = grid.length;
int m = grid[0].length;
int code = row * m + col;
stack.push(code);
grid[row][col] = '0'; // as visited
while(!stack.isEmpty())
{
code = stack.pop();
row = code / m;
col = code % m;
if(row > 0 && grid[row - 1][col] == '1') //search upward and mark adjacent '1's as '0'.
{
stack.push((row - 1) * m + col);
grid[row - 1][col] = '0'; // as visited
}
if(row < n - 1 && grid[row + 1][col] == '1') //down
{
stack.push((row + 1) * m + col);
grid[row + 1][col] = '0'; // as visited
}
if(col > 0 && grid[row][col - 1] == '1') //left
{
stack.push(row * m + col - 1);
grid[row][col - 1] = '0'; // as visited
}
if(col < m - 1 && grid[row][col + 1] == '1') //right
{
stack.push(row * m + col + 1);
grid[row][col + 1] = '0'; // as visited
}
}
}
}
Solution3 Code：
class Solution {
public int numIslands(char[][] grid) {
int count = 0;
for(int row = 0; row < grid.length; row++) {
for(int col = 0; col < grid[0].length; col++) {
if(grid[row][col] == '1') {
bfs(grid, row, col);
count++;
}
}
}
return count;
}
private void bfs(char[][] grid, int row, int col) {
Queue<Integer> queue = new LinkedList<Integer>();
int n = grid.length;
int m = grid[0].length;
int code = row * m + col;
queue.offer(code);
grid[row][col] = '0'; // as visited
while(!queue.isEmpty())
{
code = queue.poll();
row = code / m;
col = code % m;
if(row > 0 && grid[row - 1][col] == '1') //search upward and mark adjacent '1's as '0'.
{
queue.offer((row - 1) * m + col);
grid[row - 1][col] = '0'; // as visited
}
if(row < n - 1 && grid[row + 1][col] == '1') //down
{
queue.offer((row + 1) * m + col);
grid[row + 1][col] = '0'; // as visited
}
if(col > 0 && grid[row][col - 1] == '1') //left
{
queue.offer(row * m + col - 1);
grid[row][col - 1] = '0'; // as visited
}
if(col < m - 1 && grid[row][col + 1] == '1') //right
{
queue.offer(row * m + col + 1);
grid[row][col + 1] = '0'; // as visited
}
}
}
}
Solution4 Code：
class Solution {
class UF {
private int[] id;
private int[] sz; // for an id, the number of elements in that id
private int count;
public UF(char[][]grid, int m, int n) {
int N = m * n;
this.id = new int[N];
this.sz = new int[N];
this.count = 0;
// init
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if(grid[i][j] == '1') {
this.id[i * n + j] = i * n + j;
this.sz[i] = 1;
this.count++;
}
}
}
}
public void union(int p, int q) {
int p_root = find(p), q_root = find(q);
// weighted quick union
///*
if(p_root == q_root) return;
if (sz[p_root] < sz[q_root]) {
id[p_root] = q_root; sz[q_root] += sz[p_root];
} else {
id[q_root] = p_root; sz[p_root] += sz[q_root];
}
--count;
//*/
// regular
/*
if(p_root == q_root) return;
id[p_root] = q_root;
--count;
*/
}
public int find(int i) { // path compression
for (;i != id[i]; i = id[i])
id[i] = id[id[i]];
return i;
}
public boolean connected(int p, int q) {
int p_root = find(p);
int q_root = find(q);
if(p_root != q_root) return false;
else return true;
}
public int count() {
return this.count;
}
}
public int numIslands(char[][] grid) {
if(grid.length == 0 || grid[0].length == 0) return 0;
int m = grid.length, n = grid[0].length;
UF uf = new UF(grid, m, n);
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
if(grid[i][j] == '0') continue;
int p = i * n + j;
int q;
if(i > 0 && grid[i - 1][j] == '1') {
q = p - n;
uf.union(p, q);
}
if(i < m - 1 && grid[i + 1][j] == '1') {
q = p + n;
uf.union(p, q);
}
if(j > 0 && grid[i][j - 1] == '1') {
q = p - 1;
uf.union(p, q);
}
if(j < n - 1 && grid[i][j + 1] == '1') {
q = p + 1;
uf.union(p, q);
}
}
}
return uf.count();
}
}
