My python dfs solution


  • 1
    class Solution:
    # @param grid, a list of list of characters
    # @return an integer
    def numIslands(self, grid):
        if not grid or not grid[0]:return 0
        m,n=len(grid),len(grid[0])
        vis = [[False for j in xrange(n)]for i in xrange(m)]
        self.dx,self.dy=[1,-1,0,0],[0,0,1,-1]
        ans = 0 
        for i in xrange(m):
            for j in xrange(n):
                if grid[i][j]=='1' and not vis[i][j]:
                    vis[i][j]=True
                    self.dfs(i,j,grid,vis)
                    ans+=1
        return ans
    
    def dfs(self,x,y,grid,vis):
        for k in xrange(4):
            nx,ny=x+self.dx[k],y+self.dy[k]
            if nx<0 or ny<0 or nx >=len(grid) or ny>=len(grid[0])\
            or grid[nx][ny]=='0' or vis[nx][ny]: continue
            vis[nx][ny]=True
            self.dfs(nx,ny,grid,vis)

Log in to reply
 

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