当前位置：首页 > news >正文

leetcode1034. 边界着色-medium

news 2025/6/12 18:35:07

1 题目：边界着色

官方标定难度：中

给你一个大小为 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.length
n == grid[i].length
1 <= m, n <= 50
1 <= grid[i][j], color <= 1000
0 <= row < m
0 <= col < n

2 solution

深度优先搜索，判断是同一块连通区域内是否为边界值，如果是重新染色。

代码

class Solution {vector<vector<int>> g, vis;int c, cc, dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1}, m, n;void dfs(vector<vector<int>> &grid, int x, int y) {bool flag = false;vis[x][y] = 1;for (int i = 0; i < 4; i++) {int xx = x + dx[i];int yy = y + dy[i];if (xx >= 0 && xx < m && yy >= 0 && yy < n) {if (grid[xx][yy] == cc) {if(!vis[xx][yy]) dfs(grid, xx, yy);} else {flag = true;}}}if (flag || x == 0 || x == m - 1 || y == 0 || y == n -1) g[x][y] = c;}public:vector<vector<int>> colorBorder(vector<vector<int>> &grid, int row, int col, int color) {g = grid, c = color, m = grid.size(), n = grid[0].size(), cc = grid[row][col];vis = vector<vector<int>>(m, vector<int>(n));dfs(grid, row, col);return g;}
};