200.Number of Islands (M)

https://leetcode.com/problems/number-of-islands/

1.Description

Given a boolean 2D matrix,0is represented as the sea,1is represented as the island. If two 1 is adjacent, we consider them in the same island. We only consider up/down/left/right adjacent.

Find the number of islands.

Example

Given graph:

[
  [1, 1, 0, 0, 0],
  [0, 1, 0, 0, 1],
  [0, 0, 0, 1, 1],
  [0, 0, 0, 0, 0],
  [0, 0, 0, 0, 1]
]

return3.

2.Code

https://www.jiuzhang.com/problem/number-of-islands/

时间 O(NM) 空间 O(max(N,M)) 递归栈空间

Version 1: BFS

bfs 用一个queue记录“1”和他的周围是“1”的位置，把二维变成一维存储。

private int m,n;
public int numIslands(boolean[][] grid) {
    if (grid == null || grid.length == 0 || grid[0].length == 0) {
            return 0;
        }
    int result=0;
    m=grid.length;
    n=grid[0].length;
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            if(grid[i][j]==true){
                result++;
                bfs(grid,i,j);
            }
        }
    }
    return result;       
    }

public void bfs(boolean[][] grid,int x,int y){
    //first set itself as false
    grid[x][y]=false;
    LinkedList<Integer> queue=new LinkedList<Integer>();
    //transfer two-dimension to one-dimension
    int node=x*n+y;
    queue.offer(node);
    //queue record the "1" and its adjacent node
    while(!queue.isEmpty()){
        int current=queue.poll();
        //switch current to two-dimension
        int i=current/n;
        int j=current%n;
        //check upward if it is "1" set it as "0" and push into queue
        if(i>0 && grid[i-1][j]==true){
            grid[i-1][j]=false;
            queue.offer((i-1)*n+j);
        }
        //check downward
        if(i<m-1 && grid[i+1][j]==true){
            grid[i+1][j]=false;
            queue.offer((i+1)*n+j);
        }
        //check left
        if(j>0 && grid[i][j-1]==true){
            grid[i][j-1]=false;
            queue.offer(i*n+j-1);
        }
        //check right
        if(j<n-1 && grid[i][j+1]==true){
            grid[i][j+1]=false;
            queue.offer(i*n+j+1);
        }
    }
}

Version 2： BFS

算法思路： 两层for循环按行列遍历题目所给的数组，当遍历点值为1时，答案值（岛屿数量）加一，然后从这个点开始bfs，搜索所有与其相连的点。将当前点推入队列，每次从取出队头点(x,y)，将(x,y)的上下左右四个方向中所有合法点（坐标合法且值为1）推入队列，推入队列时将点数值改为0以标记已走过该点，当队列为空时，遍历结束.

Note:

1.这个题目， 在模板里里的int size = queue.size(); for(int i = 0;i< size; i++){} 其实不需要，因为两个方向数组把这个功能概括了，每次只能取这个点上下左右四个方向。

2， 这个题目不需要visited. 原因是visited过的在BFS范围内的都变成0了，不会再加进queue。变成0这个把visited功能概括了。(下面的题解还是用了TT200.)

class Node { int x; int y;
    public Node(int x, int y)
    {
        this.x = x;
        this.y = y;
    }
}

public class Solution {
    public int numIslands(char[][] grid) 
    {
        if(grid == null || grid.length == 0 || grid[0].length == 0)
        {
            return 0;
        }
        
        int height = grid.length;
        int length = grid[0].length;
        int result = 0;
        
        for(int i= 0; i< height; i++)
        {
            for(int j = 0; j< length; j++)
            {
                if(grid[i][j] == '1')
                {
                    bfsNode(grid, i, j);
                    result++;
                }
            }
        }
        return result;
        
    }
    
    
    public void bfsNode(char[][] grid, int x, int y)
    {
        int[] directionX = {0, 0, -1, 1};
        int[] directionY = {-1, 1, 0, 0};
        Queue<Node> queue = new LinkedList<Node>();
        Set<Node> visited = new HashSet<Node>();
        
        queue.offer(new Node(x, y));
        grid[x][y] = '0';
        
        while(!queue.isEmpty())
        {
            Node current = queue.poll();
            for(int j = 0; j< 4; j++)
            {
                int next_x = current.x + directionX[j];
                int next_y = current.y + directionY[j];
                if(inBound(grid, next_x, next_y))
                {
                    Node adjacent = new Node(next_x, next_y);
                    if(grid[next_x][next_y] == '1' && !visited.contains(adjacent))
                    {
                        queue.offer(adjacent);
                        visited.add(adjacent);
                        grid[next_x][next_y] = '0';
                    }
                }                    
            }            
        }
    }
    
    public boolean inBound(char[][] grid, int x, int y)
    {
        int m = grid.length;
        int n = grid[0].length;
        return x>=0 && y>=0 && x<m && y<n;
    }
}

Version 3: DFS

只要遍历一遍，碰到一个1，就把它周围所有相连的1都标记为非1，这样整个遍历过程中碰到的1的个数就是所求解。

岛屿系列问题可以用 DFS/BFS 算法或者 Union-Find 并查集算法 来解决。

用 DFS 算法解决岛屿题目是最常见的，每次遇到一个岛屿中的陆地，就用 DFS 算法吧这个岛屿「淹掉」。

如何使用 DFS 算法遍历二维数组？你把二维数组中的每个格子看做「图」中的一个节点，这个节点和周围的四个节点连通，这样二维矩阵就被抽象成了一幅网状的「图」。

为什么每次遇到岛屿，都要用 DFS 算法把岛屿「淹了」呢？主要是为了省事，避免维护 visited 数组。

图算法遍历基础 说了，遍历图是需要 visited 数组记录遍历过的节点防止走回头路。

因为 dfs 函数遍历到值为 0 的位置会直接返回，所以只要把经过的位置都设置为 0，就可以起到不走回头路的作用。

// 主函数，计算岛屿数量
int numIslands(char[][] grid) {
    int res = 0;
    int m = grid.length, n = grid[0].length;
    // 遍历 grid
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == '1') {
                // 每发现一个岛屿，岛屿数量加一
                res++;
                // 然后使用 DFS 将岛屿淹了
                dfs(grid, i, j);
            }
        }
    }
    return res;
}

// 从 (i, j) 开始，将与之相邻的陆地都变成海水
void dfs(char[][] grid, int i, int j) {
    int m = grid.length, n = grid[0].length;
    if (i < 0 || j < 0 || i >= m || j >= n) {
        // 超出索引边界
        return;
    }
    if (grid[i][j] == '0') {
        // 已经是海水了
        return;
    }
    // 将 (i, j) 变成海水
    grid[i][j] = '0';
    // 淹没上下左右的陆地
    dfs(grid, i + 1, j);
    dfs(grid, i, j + 1);
    dfs(grid, i - 1, j);
    dfs(grid, i, j - 1);
}

为什么每次遇到岛屿，都要用 DFS 算法把岛屿「淹了」呢？主要是为了省事，避免维护 visited 数组。因为 dfs 函数遍历到值为 0 的位置会直接返回，所以只要把经过的位置都设置为 0，就可以起到不走回头路的作用。

PS：这类 DFS 算法还有个别名叫做 FloodFill 算法，现在有没有觉得 FloodFill 这个名字还挺贴切的~