LeetCode-1034 边界着色
题目来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/coloring-a-border/
题目描述
给你一个大小为 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]]
提示：
m == grid.length
n == grid[i].length
1 <= m, n <= 50
1 <= grid[i][j], color <= 1000
0 <= row < m
0 <= col < n
解题思路
拿到题目粗略一看就知道这是一道图的遍历问题，想了想单纯的广度优先或者深度优先遍历怎么难度也不会是中等吧，仔细观察了一下测试用例发现用例3存在猫腻，找到了重点词，边界。
好的，那么思路有了，我们来改造一下广度优先遍历吧。
首先我们需要一个访问表，记录这个结点是否已经被访问过，但是这个访问表同时也可以记录这个结点是否是边界，这样，我们在最后时候遍历一遍访问表就可以将边界直接着色了。
创建一个同规模的visited表，-1代表未访问过，1代表是边界，0代表不是边界。
接下来就是广度优先遍历的思路了，在队列中加入起始结点，然后依次遍历队列，依次判断上下左右四个结点是不是联通，如果联通且没有访问过就加入队列，同时，通过这四个结点还可以顺便判断当前结点是不是边界。
广度优先遍历结束后，我们遍历一遍visited表，将visited表中数值是1的坐标对应的原图颜色染成题目中的color就好了。
源码展示
class Solution {
public:
vector<vector<int>> colorBorder(vector<vector<int>>& grid, int row, int col, int color) {
vector<vector<int>> vviNewGrid = grid;
vector<vector<int>> vviVisited;
queue<pair<int,int>> qpiiVisiting;
int iM = vviNewGrid.size();
int iN = vviNewGrid[0].size();
int iColor = vviNewGrid[row][col];
vviVisited.resize(iM);
for(int i=0; i<iM; i++)
{
vviVisited[i].resize(iN, -1);
}
qpiiVisiting.push({row, col});
while(!qpiiVisiting.empty())
{
int bBonudary = 0;
int iX = qpiiVisiting.front().first;
int iY = qpiiVisiting.front().second;
qpiiVisiting.pop();
if(iX - 1 >= 0)
{
if(vviVisited[iX - 1][iY] == -1)
{
if(iColor == vviNewGrid[iX - 1][iY])
{
qpiiVisiting.push({iX - 1, iY});
}
else
{
bBonudary = 1;
}
}
}
else
{
bBonudary = 1;
}
if(iX + 1 < iM)
{
if(vviVisited[iX + 1][iY] == -1)
{
if(iColor == vviNewGrid[iX + 1][iY])
{
qpiiVisiting.push({iX + 1, iY});
}
else
{
bBonudary = 1;
}
}
}
else
{
bBonudary = 1;
}
if(iY - 1 >= 0)
{
if(vviVisited[iX][iY - 1] == -1)
{
if(iColor == vviNewGrid[iX][iY - 1])
{
qpiiVisiting.push({iX, iY - 1});
}
else
{
bBonudary = 1;
}
}
}
else
{
bBonudary = 1;
}
if(iY + 1 < iN)
{
if(vviVisited[iX][iY + 1] == -1)
{
if(iColor == vviNewGrid[iX][iY + 1])
{
qpiiVisiting.push({iX, iY + 1});
}
else
{
bBonudary = 1;
}
}
}
else
{
bBonudary = 1;
}
vviVisited[iX][iY] = bBonudary;
}
for(int i = 0; i < iM; i++)
{
for(int j = 0; j < iN; j++)
{
if(vviVisited[i][j] == 1)
{
vviNewGrid[i][j] = color;
}
}
}
return vviNewGrid;
}
};
运行结果
最新文章
- 《连载 | 物联网框架ServerSuperIO教程》- 9. 协议过滤器，解决一包多发、粘包、冗余数据
- $\LaTeX$笔记：首字下沉
- Camstar Portal modeling user guid --WorkCenter workCell workStation的关系
- 用Unity实现的依赖注入
- 通过百度地图API定位--第三方开源--百度地图（一）
- C#.NET开发ActiveX控件
- JS中获取table节点的tr或td的内容
- 团队软件开发_基于windows下截屏软件关于NABC框架的特点
- [Reactive Programming] Async requests and responses in RxJS
- 统计学习方法：KNN
- 网站地图怎么做?dedecms网站地图制作方法听语音
- dojo加载树报错
- Html书写规范，基本标签使用
- 多媒体开发（6）：滤镜实现各种图片效果 | Video-Filters | avfilter | 变色
- robot framework关键词记录单（更新中）
- 运维笔记--ubuntu rm删除文件后 恢复
- AWS专线服务总结和疑问
- [20180814]慎用查看表压缩率脚本.txt
- search 重要文件路径 搜索【原】
- wsgiref分析