Number of Islands

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

Tips:

• 解法1 UnionFind:

  这个和找无向联通快差不多，就是要把二维的matrix转换成一维的然后放入map，公式是

  1d = n * i + j
  

  也要设置一个二维数组distance，使得用i + d[0] 和 j + d[1]能找到这个岛中间的四块区域，公式在代码里找。

  对于for(int[] edge : edges) 且要是岛屿（==‘1’），查找每个岛屿两边的nodes(i + d[0], j + d[1])的father，如果发现还没有合并，就Union，把第一个的father设为第二个，即map.put(fa_x, fa_y)，count--;

• 解法2 DFS：

  找到一个岛之后result++, 再往四周进行DFS，把dfs过程中碰到的岛都设为0。然后再找下一个岛，再去DFS，这样保证加的岛都不相邻。

• 解法3 BFS：

  就是把DFS换成BFS呗

Code:

UnionFind:

public class Solution {
    int m, n;
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0)  {
            return 0;  
        }
        int[][] distance = {{1,0},{-1,0},{0,1},{0,-1}};
        HashMap<Integer, Integer> map = new HashMap<>();
        m = grid.length;
        n = grid[0].length;
        int count = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1') {
                    count++;
                    map.put(i * n + j, i * n + j);
                }
            }
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] != '1') {
                    continue;
                }
                for (int[] d : distance) {
                    int x = i + d[0];
                    int y = j + d[1];
                    if (x >= 0 && y >= 0 && x < m && y < n && grid[x][y] == '1') {
                        int fa_x = find(i * n + j, map);
                        int fa_y = find(x * n + y, map);
                        if (map.get(fa_x) != map.get(fa_y)) {
                            map.put(fa_x, fa_y);
                            count--;
                        }
                    }
                }
            }
        }
        return count;
    }
    private int find (int pos, HashMap<Integer, Integer> map) {
        int father = map.get(pos);
        while (father != map.get(father)) {
            father = map.get(father);
        }
        return father;
    }
}

DFS:

public class Solution {
    private int m;
    private int n;
    public int numIslands(char[][] grid) {
        m = grid.length;
        if (m == 0) {
            return 0;
        }
        n = grid[0].length;        
        if (n == 0) {
            return 0;
        }
        int result = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1') {
                    result++;
                    dfs(i, j, grid);
                }
            }
        }
        return result;
    }
    private void dfs(int i, int j, char[][] grid) {
        if (i < 0 || j < 0 || i >= m || j >= n || grid[i][j] != '1') {
            return;
        }
        grid[i][j] = 0;
        dfs(i + 1, j, grid);
        dfs(i, j + 1, grid);
        dfs(i - 1, j, grid);
        dfs(i, j - 1, grid);
    }
}

BFS:

public int numIslands(char[][] grid) {
    int count=0;
    for(int i=0;i<grid.length;i++)
        for(int j=0;j<grid[0].length;j++){
            if(grid[i][j]=='1'){
                bfsFill(grid,i,j);
                count++;
            }
        }
    return count;
}
private void bfsFill(char[][] grid,int x, int y){
    grid[x][y]='0';
    int n = grid.length;
    int m = grid[0].length;
    LinkedList<Integer> queue = new LinkedList<Integer>();  
    int code = x*m+y;  
    queue.offer(code);  
    while(!queue.isEmpty())  
    {  
        code = queue.poll();  
        int i = code/m;  
        int j = code%m;  
        if(i>0 && grid[i-1][j]=='1')    //search upward and mark adjacent '1's as '0'.
        {  
            queue.offer((i-1)*m+j);  
            grid[i-1][j]='0';  
        }  
        if(i<n-1 && grid[i+1][j]=='1')  //down
        {  
            queue.offer((i+1)*m+j);  
            grid[i+1][j]='0';  
        }  
        if(j>0 && grid[i][j-1]=='1')  //left
        {  
            queue.offer(i*m+j-1);  
            grid[i][j-1]='0';  
        }  
        if(j<m-1 && grid[i][j+1]=='1')  //right
        {  
            queue.offer(i*m+j+1);  
            grid[i][j+1]='0';  
        }
    } 
}