class Solution:
    def colorBorder(self, grid: List[List[int]], r0: int, c0: int, color: int) -> List[List[int]]:
        g = copy.deepcopy(grid)
        m, n, target = len(grid), len(grid[0]), grid[r0][c0]
        d = {}

        def dfs(i, j):
            if (i,j) in d or i < 0 or i >= m or j < 0 or j >= n or grid[i][j] != target:
                return
            if i == 0 or i == m-1 or j == 0 or j == n-1:
                g[i][j] = color
            elif grid[i-1][j] != target or grid[i+1][j] != target or grid[i][j-1] != target or grid[i][j+1] != target:
                g[i][j] = color
            d[(i,j)] = 1
            dfs(i-1,j)
            dfs(i+1,j)
            dfs(i,j-1)
            dfs(i,j+1)

        dfs(r0, c0)
        return g