Number of Islands

LeeCode 200

BFS

class Solution:
    def numIslands(self, grid):
        """
        :type grid: List[List[str]]
        :rtype: int
        """
        """
        DFS解題有個很重要的地方為 BASE CASE: 終止條件
        
        """
        if not grid:
            return 0
        else:
            count = 0
            row = len(grid)
            col = len(grid[0])
            
            for i in range(row):
                for j in range(col):
                    if grid[i][j] == '1':
                        self.bfs(grid, i, j)
                        count += 1
            return count
    def bfs(self, grid, i, j):
        qu = collections.deque()
        qu.append((i,j))
        while qu:
            i, j = qu.popleft()
            if 0<=i<len(grid) and 0<=j<len(grid[0]) and grid[i][j]=='1':
                grid[i][j] = '#'
                qu.extend([(i-1,j),(i+1,j),(i,j-1),(i,j+1)])

DFS

class Solution:
    def numIslands(self, grid):
        """
        :type grid: List[List[str]]
        :rtype: int
        """
        """
        DFS解題有個很重要的地方為 BASE CASE: 終止條件
        
        """
        if not grid:
            return 0
        else:
            count = 0
            row = len(grid)
            col = len(grid[0])
            
            for i in range(row):
                for j in range(col):
                    if grid[i][j] == '1':
                        self.dfs(grid, i, j)
                        count += 1
            return count
    def dfs(self, grid, i, j):
        if i<0 or j<0 or i>=len(grid) or j>=len(grid[0]) or grid[i][j]!='1':
            return
        grid[i][j] = '#'
        self.dfs(grid,i+1,j) # down
        self.dfs(grid,i,j+1) # right
        self.dfs(grid,i-1,j) # up
        self.dfs(grid,i,j-1) # left