# 1034. Coloring A Border

• Time: $O(mn)$
• Space: $O(mn)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 class Solution { public: vector> colorBorder(vector>& grid, int r0, int c0, int color) { dfs(grid, r0, c0, grid[r0][c0]); for (int i = 0; i < grid.size(); ++i) for (int j = 0; j < grid[0].size(); ++j) if (grid[i][j] < 0) grid[i][j] = color; return grid; } private: void dfs(vector>& grid, int i, int j, int startColor) { if (i < 0 || i == grid.size() || j < 0 || j == grid[0].size()) return; if (grid[i][j] != startColor) return; grid[i][j] = -startColor; dfs(grid, i + 1, j, startColor); dfs(grid, i - 1, j, startColor); dfs(grid, i, j + 1, startColor); dfs(grid, i, j - 1, startColor); // If this cell is already on the boarder, it must be painted later. if (i == 0 || i == grid.size() - 1 || j == 0 || j == grid[0].size() - 1) return; if (abs(grid[i + 1][j]) == startColor && // abs(grid[i - 1][j]) == startColor && // abs(grid[i][j + 1]) == startColor && // abs(grid[i][j - 1]) == startColor) grid[i][j] = startColor; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 class Solution { public int[][] colorBorder(int[][] grid, int r0, int c0, int color) { dfs(grid, r0, c0, grid[r0][c0]); for (int i = 0; i < grid.length; ++i) for (int j = 0; j < grid[0].length; ++j) if (grid[i][j] < 0) grid[i][j] = color; return grid; } private void dfs(int[][] grid, int i, int j, int startColor) { if (i < 0 || i == grid.length || j < 0 || j == grid[0].length) return; if (grid[i][j] != startColor) return; grid[i][j] = -startColor; dfs(grid, i + 1, j, startColor); dfs(grid, i - 1, j, startColor); dfs(grid, i, j + 1, startColor); dfs(grid, i, j - 1, startColor); // If this cell is already on the boarder, it must be painted later. if (i == 0 || i == grid.length - 1 || j == 0 || j == grid[0].length - 1) return; if (Math.abs(grid[i + 1][j]) == startColor && // Math.abs(grid[i - 1][j]) == startColor && // Math.abs(grid[i][j + 1]) == startColor && // Math.abs(grid[i][j - 1]) == startColor) grid[i][j] = startColor; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 class Solution: def colorBorder(self, grid: List[List[int]], r0: int, c0: int, color: int) -> List[List[int]]: def dfs(i: int, j: int, originalColor: int) -> None: if not 0 <= i < len(grid) or not 0 <= j < len(grid[0]) or grid[i][j] != originalColor: return grid[i][j] = -originalColor dfs(i + 1, j, originalColor) dfs(i - 1, j, originalColor) dfs(i, j + 1, originalColor) dfs(i, j - 1, originalColor) if 0 < i < len(grid) - 1 and 0 < j < len(grid[0]) - 1 and \ abs(grid[i + 1][j]) == originalColor and \ abs(grid[i - 1][j]) == originalColor and \ abs(grid[i][j + 1]) == originalColor and \ abs(grid[i][j - 1]) == originalColor: grid[i][j] = originalColor dfs(r0, c0, grid[r0][c0]) for i in range(len(grid)): for j in range(len(grid[0])): if grid[i][j] < 0: grid[i][j] = color return grid