LeetCode 200. Number of Islands

题目

思路

回溯，递归函数的作用是把和当前陆地相邻的陆地都标为false。

代码

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        m = len(grid)
        if m == 0:
            return 0
        n = len(grid[0])
        res = 0
        visited = [[0 for i in range(n)] for j in range(m)]
        for i in range(m):
            for j in range(n):
                if visited[i][j] == 0 and grid[i][j] == '1':
                    res += 1
                    self.dfs(grid,i,j,visited)
        return res
    
    def dfs(self,grid,x,y,visited):
        m = len(grid)
        n = len(grid[0])        
        d = [[0,1],[1,0],[-1,0],[0,-1]]
        visited[x][y] = 1
        for i in range(4):
            newx = x + d[i][0]
            newy = y + d[i][1]
            if self.inarea(newx,newy,m,n) and visited[newx][newy] == 0 and grid[newx][newy] == '1':
                self.dfs(grid,newx,newy,visited)
        return
        
    def inarea(self,x,y,m,n):
        if 0<=x<m and 0<=y<n:
            return True
        return False