leetcode 200. 岛屿数量python

2021/11/5 17:10:54

本文主要是介绍leetcode 200. 岛屿数量python,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

题目描述:

 

 题解:DFS

是在学习回溯算法的时候遇到的这道题,但其实就是DFS的思想。

本来想通过在回溯的过程中,根据每个节点的周围节点为0和1的数量,判断该节点属于一个之前搜索过的大岛屿还是属于一个新的岛屿,但是好像不太可行。

基本思路:

对输入的grid依次进行搜索,如果遇到一个grid[i][j]=='1',说明该位置对应一个岛屿或者处在一个大岛屿中,岛屿数量加一,对该位置上下左右四个位置进行DFS,将为1的节点全都设为0,避免重复计算。

class Solution(object):
    def numIslands(self, grid):
        m = len(grid)
        n = len(grid[0])
        directions = [(0,-1),(0,1),(-1,0),(1,0)]
        number = 0
        def dfs(posx,posy):
            if 0<=posx<m and 0<=posy<n and grid[posx][posy]=='1':
                grid[posx][posy]='0'
                for dx,dy in directions:
                    newx = posx+dx
                    newy = posy+dy
                    dfs(newx,newy)

        for i in range(m):
            for j in range(n):
                if grid[i][j]=='1':
                    number = number+1
                    dfs(i,j)
        return number

 



这篇关于leetcode 200. 岛屿数量python的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程