1034. 边界着色
给你一个大小为 m x n 的整数矩阵 grid ，表示一个网格。另给你三个整数 row、col 和 color 。网格中的每个值表示该位置处的网格块的颜色。
两个网格块属于同一 连通分量 需满足下述全部条件：
两个网格块颜色相同
在上、下、左、右任意一个方向上相邻
连通分量的边界 是指连通分量中满足下述条件之一的所有网格块：
- 在上、下、左、右四个方向上与不属于同一连通分量的网格块相邻
- 在网格的边界上（第一行/列或最后一行/列）
请你使用指定颜色 color 为所有包含网格块 grid[row][col] 的 连通分量的边界 进行着色，并返回最终的网格 grid 。
public class Solution {
public int[][] ColorBorder(int[][] grid, int row, int col, int color) {
int m = grid.Length, n = grid[0].Length;
//行数和列数
bool[,] visited = new bool[m, n];
//二维数组visited，bool类型，用来记录对应位置是否遍历过了
IList<int[]> borders = new List<int[]>();
//Ilist接口来装list（可能是业务用法？）
//边界点的集合
int originalColor = grid[row][col];
//缓存，存储了格子原本的颜色
visited[row, col] = true;
//出发点肯定就是首先遍历的地方，所以在visited数组做已遍历的标记
DFS(grid, row, col, visited, borders, originalColor);
//手写的深度优先，实现在下面
//目的是确定连通分量的范围
//并且提取出边界点
for (int i = 0; i < borders.Count; i++)
{
int x = borders[i][0], y = borders[i][1];
grid[x][y] = color;
}
//遍历上色
return grid;
}
private void DFS(int[][] grid, int x, int y, bool[,] visited, IList<int[]> borders, int originalColor) {
int m = grid.Length, n = grid[0].Length;
bool isBorder = false;
int[][] direc = {new int[]{0, 1}, new int[]{0, -1}, new int[]{1, 0}, new int[]{-1, 0}};
//方向数组
for (int i = 0; i < 4; i++) {
int nx = direc[i][0] + x, ny = direc[i][1] + y;
//在方向的基础上加上起始点坐标
//循环一遍便达成了遍历四个方向的效果
//但是要记得边界判断
if (!(nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] == originalColor))
{
//判断条件
//行大于0小于m
//列大于0小于n
//这一格和起始点的颜色相等
//如果都不满足就证明是在边界上的点
isBorder = true;
}
//如果在边界内那么就得是true
else if (!visited[nx, ny])
{
//如果点不在边界内，并且之前没有被遍历到
visited[nx, ny] = true;
//确认被遍历
DFS(grid, nx, ny, visited, borders, originalColor);
//将新的坐标传入再进行深度遍历
//所谓的联通的传递性就是在这里体现的
}
}
if (isBorder)
{
borders.Add(new int[]{x, y});
//边界的点加入边界的集合
}
}
}
不说人话的典范
这题目我上午愣是审了两节课
一番搜寻后终于理解了题目但是发现自己还是不会做
把自己整麻了CV了
12月全勤的目标是真难啊
思路的话我都写在注释里了
主要是写下到底啥是连通分量的边界
首先要明确一点，连通分量的边界是在连通分量里面的
连通分量外面是不会被染色的
满足下面两个条件任意一个就行
- 1.连通分量的所占的格子 在矩阵的边界上 就算连通分量的边界
- 2.不是连通分量的格子会有四个方向上下左右
- 随便哪一个方向的格子和连通分量的格子重叠了
- 这个重叠的格子就是连通分量的边界
只要了解了这一点再来审题思考就会好很多