每日一题——1034.边界着色

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.不是连通分量的格子会有四个方向上下左右
  • 随便哪一个方向的格子和连通分量的格子重叠了
  • 这个重叠的格子就是连通分量的边界

只要了解了这一点再来审题思考就会好很多

发表评论

您的电子邮箱地址不会被公开。