Easy understanding python bfs solution


  • 0
    O

    The basic idea is first to find one land and bfs all the island to mark it as water, and then keep searching.
    Because islands would never meet each other, this method is safe and easy understanding.

    class Solution(object):
    def numIslands(self, grid):
        """
        :type grid: List[List[str]]
        :rtype: int
        """
        if not grid:
            return 0
        res = 0
        for i in xrange(len(grid)):
            for j in xrange(len(grid[0])):
                if grid[i][j]=="1":     #as long as a land is find, bfs it and mark all land to water
                    grid = self.helper(grid,i,j)
                    res +=1
        return res
    
    def helper(self,grid,i,j):
        stack=[(i,j)]
        while stack:
            temp = stack.pop()
            if temp[0]<0 or temp[0]>=len(grid) or temp[1]<0 or temp[1]>=len(grid[0]):
                continue
            if grid[temp[0]][temp[1]] == "1":
                grid[temp[0]][temp[1]] = "0"
                stack.append((temp[0]+1,temp[1]))
                stack.append((temp[0]-1,temp[1]))
                stack.append((temp[0],temp[1]+1))
                stack.append((temp[0],temp[1]-1))
        return grid

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.