# [leetcode] force deduction 200 Number of islands

2022-01-15 02:23:52

### subject

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

Here you are `'1'`（ land ） and `'0'`（ water ） A two-dimensional mesh of , Please calculate the number of islands in the grid .

Islands are always surrounded by water , And each island can only be combined by horizontal direction / Or a vertical connection between adjacent lands .

Besides , You can assume that all four sides of the mesh are surrounded by water .

Example 1：

Input ：grid = [
[“1”,“1”,“1”,“1”,“0”],
[“1”,“1”,“0”,“1”,“0”],
[“1”,“1”,“0”,“0”,“0”],
[“0”,“0”,“0”,“0”,“0”]
]
Output ：1

Example 2：

Input ：grid = [
[“1”,“1”,“0”,“0”,“0”],
[“1”,“1”,“0”,“0”,“0”],
[“0”,“0”,“1”,“0”,“0”],
[“0”,“0”,“0”,“1”,“1”]
]
Output ：3

Tips ：

• `m == grid.length`
• `n == grid[i].length`
• `1 <= m, n <= 300`
• `grid[i][j]` The value of is `'0'` or `'1'`

### Their thinking

The first time you encounter this problem, you may not know how to start , But if you write once , It must be impressive to meet you next time .

First , Understand the meaning of the question

The title gives a two-dimensional array , The definition of an island is that the top, bottom, left and right connected together in the array are character 1 The area is an island , Ask for the number of Islands .

The data range given by the title can be violent

Since the characters of an island are the same , And connect . Then we can start from one point , Gradually expand to the whole connected island . At the same time, the traversed islands are marked , Prevent double counting when traversing another point of the island next time . Let's think about the detailed process ：

1. Take each point in the array as the entry , Further expand . Therefore, recursion is needed for further expansion

2. What are the parameters of a recursive function .

All operations are performed in a two-dimensional array , So we need a two-dimensional array `grid`

The process of expansion is based on a point , Divergent expansion , So the position coordinates of the point in the two-dimensional array `x` and `y`

3. Parameters can only think of these at present , So what is the condition for the end of recursion .

When expanding , If characters are encountered `0`, Then the location must not be included in the traversed island , So the sign of the end is ： Traverse to character `0`. It is not enough , This is just a preliminary idea , It should be improved when the function is basically completed .

4. The next step is what recursive functions do .

The thing to do is to expand , How did it expand ？ Because every point is surrounded by `1` still `0` We don't know , So you need to test everything around you . Each tentative point is marked , This prevents entering the next point and returning into an endless loop , It also prevents traversing to other points on the island , Again, we will expand the double counting from this point .

Here we find the above problem , The condition for the end of recursion also needs to be added , Coordinate out of bounds , Otherwise, an error will be reported .

therefore ：

``````void dfs(vector<vector<char>> &grid, int x, int y) {
if ( The coordinates are out of bounds  || grid[x][y] == '0')
return ;
grid[x][y] = '0';	 // Mark the traversed points
dfs(grid, x - 1, y); // The point on the left
dfs(grid, x + 1, y); // The point on the right
dfs(grid, x, y - 1); // The following points
dfs(grid, x, y + 1); // The point above
}
``````

about ” entry point “ It shouldn't be hard to think , That is, traversing a two-dimensional array , When characters are encountered `1` when , Namely ” entry point “. That's why `grid` Array to address , In this way, the traversed islands will not be repeated .

There are two other ways to solve the problem , One is the iterative method . The idea is the same , I won't say much more , But a little more trouble , Time complexity is the same . The other is the union search set solution , It's also more troublesome , Similarly, there is no optimization , Omit it ...

### Code

``````class Solution {

public:
int n, m;

void dfs(vector<vector<char>> &grid, int x, int y) {

if (x < 0 || x >= n || y < 0 || y >= m || grid[x][y] == '0')
return ;
grid[x][y] = '0';
dfs(grid, x - 1, y);
dfs(grid, x + 1, y);
dfs(grid, x, y - 1);
dfs(grid, x, y + 1);
}

int numIslands(vector<vector<char>>& grid) {

n = grid.size();
if (n == 0)
return 0;
m = grid[0].size();
int k = 0;
for (int i = 0; i < n; ++ i) {

for (int j = 0; j < m; ++ j) {

if (grid[i][j] == '1') {

dfs(grid, i, j);
k ++;
}
}
}
return k;
}
};
``````

### summary

This kind of problem belongs to the problem that will be solved next time , There is a similar question in Li Kou ：130. The surrounding area . This question is a little different from this one , Just traverse the points of its four sides as “ entry point ” that will do , Also marked as other characters . Then traverse all the points , Change the point except the marking character to `X`, The marked is changed to `O` that will do . Do more similar questions , Forget to look back , This kind of problem is very easy .

https://chowdera.com/2021/12/202112122242254075.html