# 200.Number of Islands (M)

## 1.Description

Given a boolean 2D matrix,`0`is represented as the sea,`1`is 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]
]
```

return`3`.

## 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:&#x20;

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**&#x20;

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

岛屿系列问题可以用 DFS/BFS 算法或者 [Union-Find 并查集算法](https://mp.weixin.qq.com/s/gUwLfi25TYamq8AJVIopfA) 来解决。

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

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

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

[图算法遍历基础](https://mp.weixin.qq.com/s/Bh2huuuK2Z33oULZ7Qtt-Q) 说了，遍历图是需要 `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 这个名字还挺贴切的\~


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://junnie.gitbook.io/nine-chapter/4.depth-first-search/dao-yu-wen-ti/433.number-of-islands.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.