class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        if not grid:
            return 0
        m,n = len(grid) - 1, len(grid[0]) - 1
        def dfs(grid: List[List[str]], i, j):
            if i < 0 or j < 0 or i > m or j > n or grid[i][j] != '1':
                return
            grid[i][j] = 0
            dfs(grid, i, j+1)
            dfs(grid, i, j-1)
            dfs(grid, i+1, j)
            dfs(grid, i-1, j)

        numberOfIslands = 0
        for i in range(m+1):
            for j in range(n+1):
                if grid[i][j] == '1':
                    numberOfIslands +=1
                    dfs(grid, i, j)

        return numberOfIslands