题目
给你一个大小为 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]]
解题
方法一：BFS
我们要求连通域的边界，因此要知道连通域，所以遍历连通域，判断4个方向是否出现(1.矩阵边界2.不同颜色的格子),如果是，那么就是边界。
因此先判断连通域(1.不能超过矩阵边界 2.有4个任意方向有相邻颜色的格子) ，通过其他格子判断出。
判断，连通域边界，首先本身就是要连通域。如果4个方向都是连通域格子，那么就是连通域内部，不是连通域边界。
如果4个方向不全是连通域格子(当前格子是连通域格子)，那么就是边界。
代码
class Solution { public: vector<vector<int>> colorBorder(vector<vector<int>>& grid, int row, int col, int color) { int m=grid.size(),n=grid[0].size(); vector<vector<int>> res(m,vector<int>(n)); vector<vector<int>> dirs={{1,0},{-1,0},{0,1},{0,-1}}; queue<vector<int>> queue; queue.push({row,col});//从连通域中初始的格子开始遍历 while(!queue.empty()){ //获得当前格子的x,y坐标,以及初始化计数cnt vector<int> poll=queue.front(); queue.pop(); int x=poll[0],y=poll[1],cnt=0; //判断4领域的连通域个数:遍历当前格子的4个方向,如果4个方向都是连通格子，那么值不变，如果是边界，那么就填充color for(vector<int>& dir:dirs){ int nx=x+dir[0],ny=y+dir[1]; if(nx<0||nx>=m||ny<0||ny>=n) continue; if(grid[x][y]!=grid[nx][ny]) continue; else cnt++; if(res[nx][ny]==0){ //这个格子之前没有遍历过，就加入队列中 queue.push({nx,ny}); } } res[x][y]=cnt==4?grid[x][y]:color; } //给其余格子填充原来的原色 for(int i=0;i<m;i++){ for(int j=0;j<n;j++){ if(res[i][j]==0) res[i][j]=grid[i][j]; } } return res; } };
代码分步解释
这个循环中，就是 判断连通域的。
1.主要是作，判断4邻域的连通域。
2.统计当前x，y的4邻域的连通域个数
for(vector<int>& dir:dirs)
下面这个循环是判断 连通域的边界的
因为循环的内容就是连通域的格子，判断当前格子是否为连通域
while(!queue.empty())
另外补充知识
这用到了c++17的 structured bindings特性 (可以返回多个值)
queue <pair<int, int>> q; q.emplace(pair < int, int > {row, col}); auto[x, y] = q.front();
