LeetCode 733: Flood Fill (DFS/BFS Region Recoloring)
LeetCode 733DFSMatrixBFSToday we solve LeetCode 733 - Flood Fill.
Source: https://leetcode.com/problems/flood-fill/
English
Problem Summary
Given an image grid, a start cell (sr, sc), and a new color, recolor the entire 4-directionally connected component that has the same original color as image[sr][sc].
Key Insight
The component boundary is defined by the original color, not by new color or coordinates. So we must first remember oldColor = image[sr][sc] and only expand to neighbors still equal to oldColor.
Brute Force and Limitations
Checking all cells repeatedly until no change is possible is expensive and unnecessary. Graph traversal (DFS/BFS) from the seed cell naturally visits each component cell once.
Optimal Algorithm Steps
1) Read oldColor = image[sr][sc].
2) If oldColor == color, return immediately (critical to avoid infinite loops in some implementations).
3) Start DFS/BFS from (sr, sc).
4) For each popped/visited cell: repaint to color.
5) Push 4-neighbors that are in bounds and still equal to oldColor.
Complexity Analysis
Time: O(m*n) in the worst case (entire grid is one component).
Space: O(m*n) worst case due to recursion stack or queue.
Common Pitfalls
- Forgetting the oldColor == color early return.
- Expanding by comparing with color instead of oldColor.
- Missing boundary checks for neighbors.
- Using 8-direction adjacency while problem requires 4-direction only.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
private static final int[][] DIRS = {{1,0},{-1,0},{0,1},{0,-1}};
public int[][] floodFill(int[][] image, int sr, int sc, int color) {
int oldColor = image[sr][sc];
if (oldColor == color) return image;
dfs(image, sr, sc, oldColor, color);
return image;
}
private void dfs(int[][] image, int r, int c, int oldColor, int newColor) {
if (r < 0 || r >= image.length || c < 0 || c >= image[0].length) return;
if (image[r][c] != oldColor) return;
image[r][c] = newColor;
for (int[] d : DIRS) {
dfs(image, r + d[0], c + d[1], oldColor, newColor);
}
}
}func floodFill(image [][]int, sr int, sc int, color int) [][]int {
oldColor := image[sr][sc]
if oldColor == color {
return image
}
dirs := [][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
var dfs func(int, int)
dfs = func(r, c int) {
if r < 0 || r >= len(image) || c < 0 || c >= len(image[0]) {
return
}
if image[r][c] != oldColor {
return
}
image[r][c] = color
for _, d := range dirs {
dfs(r+d[0], c+d[1])
}
}
dfs(sr, sc)
return image
}class Solution {
public:
vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {
int oldColor = image[sr][sc];
if (oldColor == color) return image;
dfs(image, sr, sc, oldColor, color);
return image;
}
private:
const vector<pair<int,int>> dirs{{1,0},{-1,0},{0,1},{0,-1}};
void dfs(vector<vector<int>>& image, int r, int c, int oldColor, int newColor) {
if (r < 0 || r >= (int)image.size() || c < 0 || c >= (int)image[0].size()) return;
if (image[r][c] != oldColor) return;
image[r][c] = newColor;
for (auto [dr, dc] : dirs) {
dfs(image, r + dr, c + dc, oldColor, newColor);
}
}
};from typing import List
class Solution:
def floodFill(self, image: List[List[int]], sr: int, sc: int, color: int) -> List[List[int]]:
old = image[sr][sc]
if old == color:
return image
rows, cols = len(image), len(image[0])
dirs = ((1, 0), (-1, 0), (0, 1), (0, -1))
def dfs(r: int, c: int) -> None:
if r < 0 or r >= rows or c < 0 or c >= cols:
return
if image[r][c] != old:
return
image[r][c] = color
for dr, dc in dirs:
dfs(r + dr, c + dc)
dfs(sr, sc)
return imagevar floodFill = function(image, sr, sc, color) {
const oldColor = image[sr][sc];
if (oldColor === color) return image;
const rows = image.length;
const cols = image[0].length;
const dirs = [[1,0],[-1,0],[0,1],[0,-1]];
function dfs(r, c) {
if (r < 0 || r >= rows || c < 0 || c >= cols) return;
if (image[r][c] !== oldColor) return;
image[r][c] = color;
for (const [dr, dc] of dirs) {
dfs(r + dr, c + dc);
}
}
dfs(sr, sc);
return image;
};中文
题目概述
给定图像矩阵、起点 (sr, sc) 和目标颜色 color，把与起点 4 方向连通且颜色等于起点原色的整块区域全部染成新颜色。
核心思路
连通块扩展条件基于“原始颜色”而不是新颜色。先保存 oldColor = image[sr][sc]，遍历时只继续访问仍等于 oldColor 的邻格。
暴力解法与不足
如果每轮全图扫描找可染色点，会产生大量无效比较。以起点做 DFS/BFS 只会遍历目标连通块，结构更直接、复杂度更优。
最优算法步骤
1）读取 oldColor = image[sr][sc]。
2）若 oldColor == color 直接返回（关键剪枝）。
3）从起点发起 DFS/BFS。
4）访问到合法格子后先改色为 color。
5）继续访问 4 个方向中仍等于 oldColor 的格子。
复杂度分析
时间复杂度：O(m*n)（最坏整张图同色）。
空间复杂度：O(m*n)（递归栈或队列最坏规模）。
常见陷阱
- 忘记处理 oldColor == color 导致重复递归。
- 用新颜色作为扩展条件，导致搜索逻辑错误。
- 边界判断漏写，出现越界访问。
- 误用 8 邻域，而题目是 4 邻域。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
private static final int[][] DIRS = {{1,0},{-1,0},{0,1},{0,-1}};
public int[][] floodFill(int[][] image, int sr, int sc, int color) {
int oldColor = image[sr][sc];
if (oldColor == color) return image;
dfs(image, sr, sc, oldColor, color);
return image;
}
private void dfs(int[][] image, int r, int c, int oldColor, int newColor) {
if (r < 0 || r >= image.length || c < 0 || c >= image[0].length) return;
if (image[r][c] != oldColor) return;
image[r][c] = newColor;
for (int[] d : DIRS) {
dfs(image, r + d[0], c + d[1], oldColor, newColor);
}
}
}func floodFill(image [][]int, sr int, sc int, color int) [][]int {
oldColor := image[sr][sc]
if oldColor == color {
return image
}
dirs := [][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
var dfs func(int, int)
dfs = func(r, c int) {
if r < 0 || r >= len(image) || c < 0 || c >= len(image[0]) {
return
}
if image[r][c] != oldColor {
return
}
image[r][c] = color
for _, d := range dirs {
dfs(r+d[0], c+d[1])
}
}
dfs(sr, sc)
return image
}class Solution {
public:
vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {
int oldColor = image[sr][sc];
if (oldColor == color) return image;
dfs(image, sr, sc, oldColor, color);
return image;
}
private:
const vector<pair<int,int>> dirs{{1,0},{-1,0},{0,1},{0,-1}};
void dfs(vector<vector<int>>& image, int r, int c, int oldColor, int newColor) {
if (r < 0 || r >= (int)image.size() || c < 0 || c >= (int)image[0].size()) return;
if (image[r][c] != oldColor) return;
image[r][c] = newColor;
for (auto [dr, dc] : dirs) {
dfs(image, r + dr, c + dc, oldColor, newColor);
}
}
};from typing import List
class Solution:
def floodFill(self, image: List[List[int]], sr: int, sc: int, color: int) -> List[List[int]]:
old = image[sr][sc]
if old == color:
return image
rows, cols = len(image), len(image[0])
dirs = ((1, 0), (-1, 0), (0, 1), (0, -1))
def dfs(r: int, c: int) -> None:
if r < 0 or r >= rows or c < 0 or c >= cols:
return
if image[r][c] != old:
return
image[r][c] = color
for dr, dc in dirs:
dfs(r + dr, c + dc)
dfs(sr, sc)
return imagevar floodFill = function(image, sr, sc, color) {
const oldColor = image[sr][sc];
if (oldColor === color) return image;
const rows = image.length;
const cols = image[0].length;
const dirs = [[1,0],[-1,0],[0,1],[0,-1]];
function dfs(r, c) {
if (r < 0 || r >= rows || c < 0 || c >= cols) return;
if (image[r][c] !== oldColor) return;
image[r][c] = color;
for (const [dr, dc] of dirs) {
dfs(r + dr, c + dc);
}
}
dfs(sr, sc);
return image;
};
Comments