流通分量的_边框着色

本文主要是介绍流通分量的_边框着色，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

1、描述
2、关键字
3、思路
4、notes
5、复杂度
6、code

1、描述

给你一个大小为 m x n 的整数矩阵 grid ，表示一个网格。另给你三个整数 row、col 和 color 。网格中的每个值表示该位置处的网格块的颜色。

当两个网格块的颜色相同，而且在四个方向中任意一个方向上相邻时，它们属于同一连通分量。

连通分量的边界是指连通分量中的所有与不在分量中的网格块相邻（四个方向上）的所有网格块，或者在网格的边界上（第一行/列或最后一行/列）的所有网格块。

请你使用指定颜色 color 为所有包含网格块 grid[row][col] 的连通分量的边界进行着色，并返回最终的网格 grid 。

来源：力扣（LeetCode）
链接：
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2、关键字

流通分量，边界，涂色，更新原来的网格

3、思路

需要把当前流通分量的边界“格子”统计出来，
怎么统计？使用广度优先，输入起点，根据流通分量的条件，进行广度优先搜索，
判定是边界：通过取反的思路：把合理的都写进来，取个反。4个方向只要有一个不满足，当前格子就是边界。
然后还要记录这个格子的4个方向有没有访问过、

4、notes

1、通过边界boarder的座标来更新原来的grid网格的颜色。引用“座标”的方式。

5、复杂度

时间：O（m * n)
空间:O(N * M) 访问过没访问过

6、code

typedef pair<int,int>pii;
class Solution {
public:vector<vector<int>> colorBorder(vector<vector<int>>& grid, int row, int col, int color) {int n = grid.size();int m = grid[0].size();vector<vector<bool>>visited(n,vector<bool>(m, false));vector<pii> borders;  // 统计边界,  待会来做更新int startColor = grid[row][col];  // 连通分量的颜色，暂存起来queue<pii>que;  // 使用一个队列来实现广度优先搜索,存放的是座标 pair  ,统计用来判断是否是边界的条件que.emplace(row,col);visited[row][col] = true;int dir[5] = {1, 0, -1, 0, 1};while(!que.empty()){auto tem = que.front();que.pop();int x = tem.first;int y = tem.second;bool isBoarder = false;for(int i = 0; i < 4; i++){int nx = x + dir[i];int ny = y + dir[i + 1];// 判断当前格子是不是边界，如果当前格子的周围4方有一个“越界；大小，颜色不同”，当前格子就是边界了，// 越界了：才搞进边界数组中； 把不越界的情况 写出来，取个反，if(!(nx >= 0 && nx <n && ny >= 0 && ny <m && grid[nx][ny] == startColor)){isBoarder = true;}// 没有越界，如果没有访问过，就加到队列中，并标记成访问过了，else if(!visited[nx][ny]){que.emplace(nx, ny);visited[nx][ny] = true;}}if(isBoarder){borders.emplace_back(x, y);}}for(auto &[x, y] : borders){  // 这里直接引用边界格子的座标，直接用来更新原来的grid,grid[x][y] = color;}return grid;}
};