繼 BFS 之後來看一下 DFS。

matrix 中有一類題是用 0/1 代表海水和陸地，然後要去找出島嶼數之類的。像 1034. Coloring A Border 這題則是用數字代表不同區塊，要抓的是邊界的元素並且著色。

這題寫起來有兩個要注意的地方：

1. 邊界的判斷，如果沒有照矩陣大小去設邊界條件的話會報 error
2. visited 的記錄，可以用 set 或是相同大小的矩陣來實現

# DFS
class Solution:
    def colorBorder(self, grid: List[List[int]], row: int, col: int, color: int) -> List[List[int]]:
        m, n = len(grid), len(grid[0])
        vst = [[0 for _ in range(n)] for _ in range(m)]

        def dfs(r, c):
            if r < 0 or c < 0 or r == m or c == n:
                return True
            if vst[r][c]:
                return False
            if grid[r][c] != grid[row][col]:
                return True
            
            vst[r][c] = 1
            
            ans = False
            for dx,dy in (0,1),(1,0),(0,-1),(-1,0):
                if dfs(r+dx,c+dy):
                    ans = True
            if ans:
                grid[r][c] = color
            return False
        
        dfs(row, col)
        return grid

# 一開始靠直覺結果寫成了 BFS
class Solution:
    def colorBorder(self, grid: List[List[int]], row: int, col: int, color: int) -> List[List[int]]:
        q = [[row, col]]
        m, n= len(grid), len(grid[0])
        vst = [[0 for _ in range(n)] for _ in range(m)]
        di = [[0,1], [0,-1],[1,0],[-1,0]]
        curr = grid[row][col]

        while q:
            r, c = q.pop(0)

            for i, j in di:
                new_r, new_c = r+i, c+j
                if new_r < 0 or new_r > m-1 or new_c < 0 or new_c > n-1:
                    grid[r][c] = color
                elif vst[new_r][new_c]:
                    continue
                elif grid[new_r][new_c] != curr:
                    grid[r][c] = color
                else:
                    q.append([new_r, new_c])
                    vst[new_r][new_c] = 1

            vst[r][c] = 1

        return grid        

• DFS
  • 1034. Coloring A Border
  • 433. Minimum Genetic Mutation