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'，最終種類數(shù)count就是land數(shù)量。之所以要傳入grid判斷是否為1再assign id是因為需要將最終種類數(shù)count==land數(shù)，不需要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();
}
}
