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.不是连通分量的格子会有四个方向上下左右
- 随便哪一个方向的格子和连通分量的格子重叠了
- 这个重叠的格子就是连通分量的边界
只要了解了这一点再来审题思考就会好很多