200. Number of Islands

Solution 1: DFS + Bitmap

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        def dfsFindLand(grid, bitMap, idxX, idxY):
            isXInvalid = idxX < 0 or idxX >= len(grid)
            isYInvalid = idxY < 0 or idxY >= len(grid[0])
            if isXInvalid or isYInvalid:
                return           
            if bitMap[idxX][idxY] or grid[idxX][idxY] == '0':
                return

            bitMap[idxX][idxY] = True
            dfsFindLand(grid, bitMap, idxX+1, idxY)
            dfsFindLand(grid, bitMap, idxX,   idxY+1)
            dfsFindLand(grid, bitMap, idxX-1, idxY)
            dfsFindLand(grid, bitMap, idxX,   idxY-1)
        
        m = len(grid)
        n = len(grid[0])
        isPointVisited = [[False for i in range(n)] for j in range(m)]
        numOfIsland = 0
        for i in range(m):
            for j in range(n):
                if not isPointVisited[i][j] and grid[i][j] == '1':
                    numOfIsland += 1
                    dfsFindLand(grid, isPointVisited, i, j)
        return numOfIsland

Time Complexity: O(N^2)
Space Complexity: O(N)

Solution 2: DFS without Bitmap

Time Complexity: O(N^2)
Space Complexity: O(N)

Solution 3: BFS without Bitmap

Time Complexity: O(N^2)
Space Complexity: O(N)

Reference

https://www.cnblogs.com/grandyang/p/4402656.html