当前位置：网站首页>Leetcode200 - find detailed explanation of the number of islands

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 .

analysis ：

1. Numbers 1 The part of is the mainland , Numbers 0 Part of the island

2. The mainland can only be compared with the upper, lower, left and right 1 form , Diagonally 1 Cannot form

Example

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

analysis

DFS

For example 2, First of all, according to the rules, you can see , There are three islands in total

Use DFS The idea of method , First First step You can set a pointer , The pointer initially points to （0,0） The location of , Because it can only be up, down, left and right 1 Can form an island , therefore The second step take （0,0） The position is up, down, left and right 1 become 0, Prove that 1 Already with （0,0） The location constitutes the island , then The third step Then point the pointer to （0,1） Position shifting , Step four Similarly, the top, bottom, left and right 1 become 0, And then move , Up, down, left and right until the current position is 0 No, 1 when , It means that the current island has ended , Continue to move to find the next island , Until we reach the end of the whole two-dimensional array .

According to the example 2 Detailed analysis

When the pointer continues to move to （0,2） Location time , The top, bottom, left and right of this position are 0, Explain that there is no consistent 1 Can continue to form islands , So at this time, the island 1 All have been found .

Keep moving the pointer , Go to the next island ......

When the pointer moves to （2,2） Location time , There is 1, It shows that new islands have appeared , Do the same 1 change 0 The operation of , But at this time, up, down, left and right 0, It means that all the islands have been found , This is a “ Small island ”

Also continue to move the pointer , Go to the next island ......

When the pointer moves to （3,3） The position of appears again 1, It means that new islands appear , Put up, down, left and right 1 Turn into 0

When the pointer moves to the end , All areas have been traversed

BFS

BFS The process of method is also up and down 1 The process of , But here we need queues , The first step is to point the pointer to （0,0） The location of , The second step is to put the coordinates of this position into the queue , The third step is to take out the coordinate position from the queue , The fourth step is to set the coordinates up, down, left and right as 1 Put the position of in the queue

The fifth step will be up, down, left and right 1 And the position of that becomes 0, Step 6 take out the first element of the queue , And make it up, down, left and right 1 Place in the queue , The seventh step will be 1 Your position becomes 0

Take out the coordinates in the queue in turn , And judge whether there is 1, Until there are no coordinates in the queue

Move the pointer , Until the next one is 1 The location of , Then find the second island

Move the pointer , Find the third island

Code

DFS

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        if grid is None or len(grid) == 0:  #  If the entire area is empty , There are no islands , Go straight back to 0
            return 0
        
        result = 0  #  Record the number of Islands 
        row = len(grid)  #  Number of rows in the whole area 
        col = len(grid[0])  #  The number of columns in the entire region 
        
        #  use 2 individual for Loop through the entire region 
        for i in range(0, row):
            for j in range(0, col):
                if grid[i][j] == '1':  #  Found a new island 
                    result += 1
                    self.dfs(grid, i, j, row, col) 
        return result

    def dfs(self, grid, x, y, row, col): # (x,y) Is the position indicated by the current pointer 
        # x,y Stop the cycle directly when outside the area 
        if x<0 or y<0 or x>=row or y>= col or grid[x][y]=='0':
            return
        
        grid[x][y] = '0'  # take 1 change 0

        #  Find up, down, left and right 1 The position of the becomes 0
        self.dfs(grid, x-1, y, row, col)  #  Left change 0
        self.dfs(grid, x+1, y, row, col)  #  The right side changes 0
        self.dfs(grid, x, y-1, row, col)  #  The upper side changes 0
        self.dfs(grid, x, y+1, row, col)  #  Change below 0

BFS

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        if grid is None or len(grid) == 0:  #  If the entire area is empty , There are no islands , Go straight back to 0
            return 0
        
        result = 0  #  Record the number of Islands 
        row = len(grid)  #  Number of rows in the whole area 
        col = len(grid[0])  #  The number of columns in the entire region 
        queue = []
        for i in range(0, row):
            for j in range(0, col):
                if grid[i][j] == '1':
                    result += 1
                    queue.append([i,j])
                    grid[i][j] = '0'
                    while len(queue) > 0:
                        cur = queue.pop()
                        x = cur[0]
                        y = cur[1]
                        if x-1 >= 0 and grid[x-1][y] == '1':
                            queue.append([x-1,y])
                            grid[x-1][y] = '0'
                        if y-1 >= 0 and grid[x][y-1] == '1':
                            queue.append([x,y-1])
                            grid[x][y-1] = '0'
                        if x+1 < row and grid[x+1][y] == '1':
                            queue.append([x+1,y])
                            grid[x+1][y] = '0'
                        if y+1 < col and grid[x][y+1] == '1':
                            queue.append([x,y+1])
                            grid[x][y+1] = '0'
        return result

原网站

版权声明
本文为[Aries by]所创，转载请带上原文链接，感谢
https://yzsam.com/2022/206/202207252355027629.html