题目描述
给出一个二维整数网格 grid
,网格中的每个值表示该位置处的网格块的颜色。
只有当两个网格块的颜色相同,而且在四个方向中任意一个方向上相邻时,它们属于同一连通分量。
连通分量的边界是指连通分量中的所有与不在分量中的正方形相邻(四个方向上)的所有正方形,或者在网格的边界上(第一行/列或最后一行/列)的所有正方形。
给出位于 (r0, c0)
的网格块和颜色 color
,使用指定颜色 color
为所给网格块的连通分量的边界进行着色,并返回最终的网格 grid
。
样例
输入:grid = [[1,1],[1,2]], r0 = 0, c0 = 0, color = 3
输出:[[3, 3], [3, 2]]
输入:grid = [[1,2,2],[2,3,2]], r0 = 0, c0 = 1, color = 3
输出:[[1, 3, 3], [2, 3, 3]]
输入:grid = [[1,1,1],[1,1,1],[1,1,1]], r0 = 1, c0 = 1, color = 2
输出:[[2, 2, 2], [2, 1, 2], [2, 2, 2]]
限制
1 <= grid.length <= 50
1 <= grid[0].length <= 50
1 <= grid[i][j] <= 1000
0 <= r0 < grid.length
0 <= c0 < grid[0].length
1 <= color <= 1000
算法
(递归遍历) $O(rc)$
- 从
(r0, c0)
开始向四个方向递归遍历。维护一个全局的二维数组v
,表示遍历的状态。 v[x][y]
为 -1 则表示尚未遍历;为 0 则表示已经遍历过了,但不能染色;为color
则表示已经染色了。- 最后把数组
v
的结果与grid
合并。
时间复杂度
- 每个位置最多遍历一次,故时间复杂度为 $O(rc)$。
空间复杂度
- 需要额外 $O(rc)$ 的空间存储数组
v
,以及递归的系统栈。
C++ 代码
class Solution {
public:
const int dx[4] = {0, 1, 0, -1};
const int dy[4] = {1, 0, -1, 0};
void solve(int x, int y, int color,
const vector<vector<int>>& grid,
vector<vector<int>>& v) {
v[x][y] = 0;
for (int k = 0; k < 4; k++) {
int tx = x + dx[k];
int ty = y + dy[k];
if (tx < 0 || tx >= grid.size()
|| ty < 0 || ty >= grid[0].size()
|| grid[tx][ty] != grid[x][y]) {
v[x][y] = color;
continue;
}
if (v[tx][ty] == -1)
solve(tx, ty, color, grid, v);
}
}
vector<vector<int>> colorBorder(vector<vector<int>>& grid, int r0, int c0, int color) {
int r = grid.size(), c = grid[0].size();
vector<vector<int>> v(r, vector<int>(c, -1));
solve(r0, c0, color, grid, v);
for (int i = 0; i < r; i++)
for (int j = 0; j < c; j++)
if (v[i][j] > 0)
grid[i][j] = v[i][j];
return grid;
}
};