# 200. Number of Islands
###### tags: `DFS`,`leetcode study group`, `2020`

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        res = 0 
        for row in range(len(grid)):
            for col in range(len(grid[0])):
                if grid[row][col] == "1":
                    self.dfs(grid, row, col)
                    res += 1
        return res
    
    def dfs(self, grid, i, j):
        grid[i][j] = "0"
        dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]] # neighborhood 
        for dir in dirs:
            nr, nc = i + dir[0], j +dir[1]
            if nr >= 0 and nc >= 0 and nr < len(grid) and nc <len(grid[0]):
                if grid[nr][nc] == "1":
                    self.dfs(grid, nr, nc)

#### Time Complexity
O(M x N), M is the number of rows and N is the number of columns
#### Space Complexity
O(M x N) in case that the grid map is filled with lands where DFS goes by M x N deep.