题解 | #岛屿数量#

DFS: once '1' is found then trigger dfs() to search all adjacent '1' and flip them as '0', since all adjacent '1' are regarded as one island. Use for loop to go through the grid.
Big O time complexity as O(rc) r- number of rows, c-number of columns.
BIg O space complexity as:O(rc). since in the worst case, the whole grid are filled with '1' then the dfs searching depth would be area of grid: r*c

class Solution:
    def solve(self , grid ):

        # write code heren 
        nr=len(grid)
        nc=len(grid[0])
        nums=0
        def dfs(grid,r,c):
            grid[r][c]=0
            # flip adjacent 1 to be zero since they are connected and regarded as one island
            for (x,y) in [(r-1,c),(r+1,c),(r,c-1),(r,c+1)]:
                if 0<=x<nr and 0<=y<nc and grid[x][y]=='1':
                    dfs(grid,x,y)

        for i in range(nr):
            for j in range(nc):
                if grid[i][j]=='1':
                    nums+=1
                    dfs(grid,i,j)
        return nums