LC 1034 [M] Coloring A Border - ALawliet/algorithms GitHub Wiki

class Solution:
    def colorBorder(self, grid: List[List[int]], row: int, col: int, color: int) -> List[List[int]]:
        n_rows = len(grid)
        n_cols = len(grid[0])
        
        visited = set()

        def dfs(r, c):
            if (r, c) in visited: return True
            
            # not (in bounds and adjacent same color)
            if not (0 <= r < n_rows and 0 <= c < n_cols and grid[r][c] == grid[row][col]):
                return False
            
            visited.add( (r, c) )
            
            # cells on border have < 4 neighbors
            # so if dfs fails for any one of the directions
            # it implies that either the current cell was at a boundary or adjacent to a cell of different color and hence number of "True" returned by calls shall be less than 4. in this case, we change the color.
            if dfs(r+1, c) + dfs(r-1, c) + dfs(r, c+1) + dfs(r, c-1) < 4:
                grid[r][c] = color
                
            return True
        
        dfs(row, col)
        
        return grid