LeetCode 1034: Coloring A Border (DFS Component Border Detection)
LeetCode 1034GraphDFSToday we solve LeetCode 1034 - Coloring A Border.
Source: https://leetcode.com/problems/coloring-a-border/
English
Problem Summary
We start from (row, col), collect its connected component of same color, and repaint only the border cells of that component with the new color.
Key Insight
A cell is a border if it is on the grid edge, or it has at least one 4-direction neighbor with a different color. DFS can traverse the whole component and decide border status per cell.
Algorithm
- Save the original color of the component.
- DFS only through cells with that original color.
- For each visited cell, mark border if it touches outside or different-color neighbor.
- Repaint only recorded border cells.
Complexity Analysis
Let component size be k.
Time: O(k).
Space: O(k) for visited and recursion stack.
Common Pitfalls
- Recoloring during DFS and breaking neighbor checks.
- Traversing into different-color cells.
- Forgetting that edge cells are always border.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
private int m, n;
private int origin;
private boolean[][] vis;
private final int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};
public int[][] colorBorder(int[][] grid, int row, int col, int color) {
m = grid.length;
n = grid[0].length;
origin = grid[row][col];
vis = new boolean[m][n];
java.util.List<int[]> border = new java.util.ArrayList<>();
dfs(grid, row, col, border);
for (int[] cell : border) {
grid[cell[0]][cell[1]] = color;
}
return grid;
}
private void dfs(int[][] grid, int r, int c, java.util.List<int[]> border) {
vis[r][c] = true;
boolean isBorder = (r == 0 || r == m - 1 || c == 0 || c == n - 1);
for (int[] d : dirs) {
int nr = r + d[0], nc = c + d[1];
if (nr < 0 || nr >= m || nc < 0 || nc >= n) {
isBorder = true;
continue;
}
if (grid[nr][nc] != origin) {
isBorder = true;
continue;
}
if (!vis[nr][nc]) dfs(grid, nr, nc, border);
}
if (isBorder) border.add(new int[]{r, c});
}
}func colorBorder(grid [][]int, row int, col int, color int) [][]int {
m, n := len(grid), len(grid[0])
origin := grid[row][col]
vis := make([][]bool, m)
for i := range vis {
vis[i] = make([]bool, n)
}
dirs := [][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
border := make([][2]int, 0)
var dfs func(int, int)
dfs = func(r, c int) {
vis[r][c] = true
isBorder := r == 0 || r == m-1 || c == 0 || c == n-1
for _, d := range dirs {
nr, nc := r+d[0], c+d[1]
if nr < 0 || nr >= m || nc < 0 || nc >= n {
isBorder = true
continue
}
if grid[nr][nc] != origin {
isBorder = true
continue
}
if !vis[nr][nc] {
dfs(nr, nc)
}
}
if isBorder {
border = append(border, [2]int{r, c})
}
}
dfs(row, col)
for _, p := range border {
grid[p[0]][p[1]] = color
}
return grid
}class Solution {
public:
int m, n, origin;
vector<vector<bool>> vis;
vector<pair<int,int>> border;
int dr[4] = {1, -1, 0, 0};
int dc[4] = {0, 0, 1, -1};
vector<vector<int>> colorBorder(vector<vector<int>>& grid, int row, int col, int color) {
m = grid.size();
n = grid[0].size();
origin = grid[row][col];
vis.assign(m, vector<bool>(n, false));
dfs(grid, row, col);
for (auto &p : border) grid[p.first][p.second] = color;
return grid;
}
void dfs(vector<vector<int>>& grid, int r, int c) {
vis[r][c] = true;
bool isBorder = (r == 0 || r == m - 1 || c == 0 || c == n - 1);
for (int k = 0; k < 4; ++k) {
int nr = r + dr[k], nc = c + dc[k];
if (nr < 0 || nr >= m || nc < 0 || nc >= n) {
isBorder = true;
continue;
}
if (grid[nr][nc] != origin) {
isBorder = true;
continue;
}
if (!vis[nr][nc]) dfs(grid, nr, nc);
}
if (isBorder) border.push_back({r, c});
}
};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])
origin = grid[row][col]
vis = [[False] * n for _ in range(m)]
border = []
def dfs(r: int, c: int) -> None:
vis[r][c] = True
is_border = r == 0 or r == m - 1 or c == 0 or c == n - 1
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
nr, nc = r + dr, c + dc
if nr < 0 or nr >= m or nc < 0 or nc >= n:
is_border = True
continue
if grid[nr][nc] != origin:
is_border = True
continue
if not vis[nr][nc]:
dfs(nr, nc)
if is_border:
border.append((r, c))
dfs(row, col)
for r, c in border:
grid[r][c] = color
return grid/**
* @param {number[][]} grid
* @param {number} row
* @param {number} col
* @param {number} color
* @return {number[][]}
*/
var colorBorder = function(grid, row, col, color) {
const m = grid.length, n = grid[0].length;
const origin = grid[row][col];
const vis = Array.from({ length: m }, () => Array(n).fill(false));
const border = [];
const dirs = [[1,0],[-1,0],[0,1],[0,-1]];
const dfs = (r, c) => {
vis[r][c] = true;
let isBorder = r === 0 || r === m - 1 || c === 0 || c === n - 1;
for (const [dr, dc] of dirs) {
const nr = r + dr, nc = c + dc;
if (nr < 0 || nr >= m || nc < 0 || nc >= n) {
isBorder = true;
continue;
}
if (grid[nr][nc] !== origin) {
isBorder = true;
continue;
}
if (!vis[nr][nc]) dfs(nr, nc);
}
if (isBorder) border.push([r, c]);
};
dfs(row, col);
for (const [r, c] of border) {
grid[r][c] = color;
}
return grid;
};中文
题目概述
从 (row, col) 出发，找到与起点同色的连通块，只把这个连通块的边界格子涂成新颜色。
核心思路
边界格子的判定有两种情况：在矩阵外圈，或者四联通邻居里存在不同颜色。用 DFS 只遍历同色连通块，同时判断每个格子是否边界。
算法步骤
- 记录起点原色 origin。
- DFS 仅进入颜色等于 origin 的格子。
- 若当前格子触边或邻居异色，记为边界。
- DFS 结束后统一给边界格子上色。
复杂度分析
设连通块大小为 k。
时间复杂度：O(k)。
空间复杂度：O(k)（访问标记与递归栈）。
常见陷阱
- DFS 过程中直接改色，导致后续判定混乱。
- 误走到非原色格子。
- 忘记最外圈格子天然是边界。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
private int m, n;
private int origin;
private boolean[][] vis;
private final int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};
public int[][] colorBorder(int[][] grid, int row, int col, int color) {
m = grid.length;
n = grid[0].length;
origin = grid[row][col];
vis = new boolean[m][n];
java.util.List<int[]> border = new java.util.ArrayList<>();
dfs(grid, row, col, border);
for (int[] cell : border) {
grid[cell[0]][cell[1]] = color;
}
return grid;
}
private void dfs(int[][] grid, int r, int c, java.util.List<int[]> border) {
vis[r][c] = true;
boolean isBorder = (r == 0 || r == m - 1 || c == 0 || c == n - 1);
for (int[] d : dirs) {
int nr = r + d[0], nc = c + d[1];
if (nr < 0 || nr >= m || nc < 0 || nc >= n) {
isBorder = true;
continue;
}
if (grid[nr][nc] != origin) {
isBorder = true;
continue;
}
if (!vis[nr][nc]) dfs(grid, nr, nc, border);
}
if (isBorder) border.add(new int[]{r, c});
}
}func colorBorder(grid [][]int, row int, col int, color int) [][]int {
m, n := len(grid), len(grid[0])
origin := grid[row][col]
vis := make([][]bool, m)
for i := range vis {
vis[i] = make([]bool, n)
}
dirs := [][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
border := make([][2]int, 0)
var dfs func(int, int)
dfs = func(r, c int) {
vis[r][c] = true
isBorder := r == 0 || r == m-1 || c == 0 || c == n-1
for _, d := range dirs {
nr, nc := r+d[0], c+d[1]
if nr < 0 || nr >= m || nc < 0 || nc >= n {
isBorder = true
continue
}
if grid[nr][nc] != origin {
isBorder = true
continue
}
if !vis[nr][nc] {
dfs(nr, nc)
}
}
if isBorder {
border = append(border, [2]int{r, c})
}
}
dfs(row, col)
for _, p := range border {
grid[p[0]][p[1]] = color
}
return grid
}class Solution {
public:
int m, n, origin;
vector<vector<bool>> vis;
vector<pair<int,int>> border;
int dr[4] = {1, -1, 0, 0};
int dc[4] = {0, 0, 1, -1};
vector<vector<int>> colorBorder(vector<vector<int>>& grid, int row, int col, int color) {
m = grid.size();
n = grid[0].size();
origin = grid[row][col];
vis.assign(m, vector<bool>(n, false));
dfs(grid, row, col);
for (auto &p : border) grid[p.first][p.second] = color;
return grid;
}
void dfs(vector<vector<int>>& grid, int r, int c) {
vis[r][c] = true;
bool isBorder = (r == 0 || r == m - 1 || c == 0 || c == n - 1);
for (int k = 0; k < 4; ++k) {
int nr = r + dr[k], nc = c + dc[k];
if (nr < 0 || nr >= m || nc < 0 || nc >= n) {
isBorder = true;
continue;
}
if (grid[nr][nc] != origin) {
isBorder = true;
continue;
}
if (!vis[nr][nc]) dfs(grid, nr, nc);
}
if (isBorder) border.push_back({r, c});
}
};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])
origin = grid[row][col]
vis = [[False] * n for _ in range(m)]
border = []
def dfs(r: int, c: int) -> None:
vis[r][c] = True
is_border = r == 0 or r == m - 1 or c == 0 or c == n - 1
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
nr, nc = r + dr, c + dc
if nr < 0 or nr >= m or nc < 0 or nc >= n:
is_border = True
continue
if grid[nr][nc] != origin:
is_border = True
continue
if not vis[nr][nc]:
dfs(nr, nc)
if is_border:
border.append((r, c))
dfs(row, col)
for r, c in border:
grid[r][c] = color
return grid/**
* @param {number[][]} grid
* @param {number} row
* @param {number} col
* @param {number} color
* @return {number[][]}
*/
var colorBorder = function(grid, row, col, color) {
const m = grid.length, n = grid[0].length;
const origin = grid[row][col];
const vis = Array.from({ length: m }, () => Array(n).fill(false));
const border = [];
const dirs = [[1,0],[-1,0],[0,1],[0,-1]];
const dfs = (r, c) => {
vis[r][c] = true;
let isBorder = r === 0 || r === m - 1 || c === 0 || c === n - 1;
for (const [dr, dc] of dirs) {
const nr = r + dr, nc = c + dc;
if (nr < 0 || nr >= m || nc < 0 || nc >= n) {
isBorder = true;
continue;
}
if (grid[nr][nc] !== origin) {
isBorder = true;
continue;
}
if (!vis[nr][nc]) dfs(nr, nc);
}
if (isBorder) border.push([r, c]);
};
dfs(row, col);
for (const [r, c] of border) {
grid[r][c] = color;
}
return grid;
};
Comments