> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/exhaustive-search/number-of-islands.md).

# Number of Islands

<https://leetcode.com/problems/number-of-islands/description/>

> 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

## Thoughts

每次遇到"1", 把它能遍历到的所有"1"都置为0, 以后再遇到"1"说明和之前的不是一个集合的.

## Code

```
class Solution {
    int[][] dirs = new int[][]{{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
    private void dfs(char[][] grid, int i, int j) {
        int m = grid.length, n = m == 0 ? 0 : grid[0].length;
        if (i >= 0 && i < m && j >= 0 && j < n && grid[i][j] == '1') {
            grid[i][j] = '0';
            for (int[] dir : dirs) {
                dfs(grid, i + dir[0], j + dir[1]);
            }
        }
    }

    public int numIslands(char[][] grid) {
        int m = grid.length, n = m == 0 ? 0 : 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') {
                    dfs(grid, i, j);
                    count++;
                }
            }
        }

        return count;
    }
}
```

## Analysis

Errors:

1. 必须四个方向都遍历

时间复杂度O(MN)