当前位置:网站首页>[leetcode] force deduction 200 Number of islands

[leetcode] force deduction 200 Number of islands

2022-01-15 02:23:52 Listen to the passing flow

subject

Topic link :

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

then , Think about it

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) {
     // Address here 
	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 .

版权声明
本文为[Listen to the passing flow]所创,转载请带上原文链接,感谢
https://chowdera.com/2021/12/202112122242254075.html

随机推荐