| comments | difficulty | edit_url | rating | source | tags | ||||
|---|---|---|---|---|---|---|---|---|---|
true |
中等 |
1578 |
第 134 场周赛 Q2 |
|
给你一个大小为 m x n 的整数矩阵 grid ，表示一个网格。另给你三个整数 row、col 和 color 。网格中的每个值表示该位置处的网格块的颜色。
如果两个方块在任意 4 个方向上相邻，则称它们 相邻 。
如果两个方块具有相同的颜色且相邻，它们则属于同一个 连通分量 。
连通分量的边界 是指连通分量中满足下述条件之一的所有网格块：
- 在上、下、左、右任意一个方向上与不属于同一连通分量的网格块相邻
- 在网格的边界上（第一行/列或最后一行/列）
请你使用指定颜色 color 为所有包含网格块 grid[row][col] 的 连通分量的边界 进行着色。
并返回最终的网格 grid 。
示例 1：
输入：grid = [[1,1],[1,2]], row = 0, col = 0, color = 3 输出：[[3,3],[3,2]]
示例 2：
输入：grid = [[1,2,2],[2,3,2]], row = 0, col = 1, color = 3 输出：[[1,3,3],[2,3,3]]
示例 3：
输入：grid = [[1,1,1],[1,1,1],[1,1,1]], row = 1, col = 1, color = 2 输出：[[2,2,2],[2,1,2],[2,2,2]]
提示：
m == grid.lengthn == grid[i].length1 <= m, n <= 501 <= grid[i][j], color <= 10000 <= row < m0 <= col < n
我们从位置
时间复杂度
class Solution:
def colorBorder(
self, grid: List[List[int]], row: int, col: int, color: int
) -> List[List[int]]:
def dfs(i: int, j: int, c: int) -> None:
vis[i][j] = True
for a, b in pairwise((-1, 0, 1, 0, -1)):
x, y = i + a, j + b
if 0 <= x < m and 0 <= y < n:
if not vis[x][y]:
if grid[x][y] == c:
dfs(x, y, c)
else:
grid[i][j] = color
else:
grid[i][j] = color
m, n = len(grid), len(grid[0])
vis = [[False] * n for _ in range(m)]
dfs(row, col, grid[row][col])
return gridclass Solution {
private int[][] grid;
private int color;
private int m;
private int n;
private boolean[][] vis;
public int[][] colorBorder(int[][] grid, int row, int col, int color) {
this.grid = grid;
this.color = color;
m = grid.length;
n = grid[0].length;
vis = new boolean[m][n];
dfs(row, col, grid[row][col]);
return grid;
}
private void dfs(int i, int j, int c) {
vis[i][j] = true;
int[] dirs = {-1, 0, 1, 0, -1};
for (int k = 0; k < 4; ++k) {
int x = i + dirs[k], y = j + dirs[k + 1];
if (x >= 0 && x < m && y >= 0 && y < n) {
if (!vis[x][y]) {
if (grid[x][y] == c) {
dfs(x, y, c);
} else {
grid[i][j] = color;
}
}
} else {
grid[i][j] = color;
}
}
}
}class Solution {
public:
vector<vector<int>> colorBorder(vector<vector<int>>& grid, int row, int col, int color) {
int m = grid.size();
int n = grid[0].size();
bool vis[m][n];
memset(vis, false, sizeof(vis));
int dirs[5] = {-1, 0, 1, 0, -1};
function<void(int, int, int)> dfs = [&](int i, int j, int c) {
vis[i][j] = true;
for (int k = 0; k < 4; ++k) {
int x = i + dirs[k];
int y = j + dirs[k + 1];
if (x >= 0 && x < m && y >= 0 && y < n) {
if (!vis[x][y]) {
if (grid[x][y] == c) {
dfs(x, y, c);
} else {
grid[i][j] = color;
}
}
} else {
grid[i][j] = color;
}
}
};
dfs(row, col, grid[row][col]);
return grid;
}
};func colorBorder(grid [][]int, row int, col int, color int) [][]int {
m, n := len(grid), len(grid[0])
vis := make([][]bool, m)
for i := range vis {
vis[i] = make([]bool, n)
}
dirs := [5]int{-1, 0, 1, 0, -1}
var dfs func(int, int, int)
dfs = func(i, j, c int) {
vis[i][j] = true
for k := 0; k < 4; k++ {
x, y := i+dirs[k], j+dirs[k+1]
if x >= 0 && x < m && y >= 0 && y < n {
if !vis[x][y] {
if grid[x][y] == c {
dfs(x, y, c)
} else {
grid[i][j] = color
}
}
} else {
grid[i][j] = color
}
}
}
dfs(row, col, grid[row][col])
return grid
}function colorBorder(grid: number[][], row: number, col: number, color: number): number[][] {
const m = grid.length;
const n = grid[0].length;
const vis = new Array(m).fill(0).map(() => new Array(n).fill(false));
const dirs = [-1, 0, 1, 0, -1];
const dfs = (i: number, j: number, c: number) => {
vis[i][j] = true;
for (let k = 0; k < 4; ++k) {
const x = i + dirs[k];
const y = j + dirs[k + 1];
if (x >= 0 && x < m && y >= 0 && y < n) {
if (!vis[x][y]) {
if (grid[x][y] == c) {
dfs(x, y, c);
} else {
grid[i][j] = color;
}
}
} else {
grid[i][j] = color;
}
}
};
dfs(row, col, grid[row][col]);
return grid;
}