给你一个大小为 m x n 的整数矩阵 grid ，表示一个网格。另给你三个整数 row、col 和 color 。网格中的每个值表示该位置处的网格块的颜色。
两个网格块属于同一 连通分量 需满足下述全部条件：
- 两个网格块颜色相同
- 在上、下、左、右任意一个方向上相邻
连通分量的边界 是指连通分量中满足下述条件之一的所有网格块：
- 在上、下、左、右任意一个方向上与不属于同一连通分量的网格块相邻
- 在网格的边界上（第一行/列或最后一行/列）
请你使用指定颜色 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
Related Topics
👍 147👎 0
海星，理解了题意的话就比较简单了（补充更新）
给个图吧，题目写得太拗口了
给出如图的矩阵grid[][]，给出了对应坐标row = 3，col = 4，和一个color随便是什么，并不重要
要求把row, col位置连通分量的边界的值修改为color值
题目中并给出了连通分量的定义，即四个方向中任意一个方向上相邻，且值相等的区块，那么自然的边界的定义我们就能理解出来，如果上下左右4个方向上有任意一个和连通分量的值不同的话，那么就可以说明这个格子是边框，且如果这个连通分量格子本身是矩阵的边界的话，那么他也是边框
那么按照题意，这个图上的应该要修改的位置就是如下
理解了这层的话就好办了，直接上DFS
代码
class Solution {
int[][] grid;
int m;
int n;
int connectedComponentValue;
int borderColor;
boolean[][] visited;
int[][] dir = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};
public int[][] colorBorder(int[][] grid, int row, int col, int color) {
this.grid = grid;
m = grid.length;
n = grid[0].length;
visited = new boolean[m][n];
connectedComponentValue = grid[row][col];
borderColor = color;
dfs(row,col);
return this.grid;
}
public void dfs(int row, int col){
boolean borderFlag = false;
visited[row][col] = true;
for (int[] ints : dir) {
int x = row + ints[0];
int y = col + ints[1];
if (isOutOfBoundary(x,y)){
borderFlag = true;
continue;
}
if (visited[x][y]){
continue;
}
if (grid[x][y] != connectedComponentValue){
borderFlag = true;
continue;
}
dfs(x,y);
}
if (borderFlag){
grid[row][col] = borderColor;
}
}
// boolean isEdge(int row, int col){
// return row == 0 || col == 0 || row == m-1 || col==n-1;
// }
boolean isOutOfBoundary(int row, int col){
return row < 0 || col < 0 || row >= m || col >= n;
}
}
补充更新个小细节
isOutOfBoundary判断需要在visited[x][y]之前，为了防止发生越界错误grid[x][y] != connectedComponentValue判断需要在visited[x][y]之后，深搜会先改变染色掉之前访问到的格子，如果不先判断visited[x][y]的话会导致类似缩圈的效果，把整个连通区域全都染色
发表评论