# 1034. Coloring A Border

Given a 2-dimensional `grid` of integers, each value in the grid represents the color of the grid square at that location.

Two squares belong to the same  connected component  if and only if they have the same color and are next to each other in any of the 4 directions.

The  border  of a connected component is all the squares in the connected component that are either 4-directionally adjacent to a square not in the component, or on the boundary of the grid (the first or last row or column).

Given a square at location `(r0, c0)` in the grid and a `color`, color the border of the connected component of that square with the given `color`, and return the final `grid`.

Example 1:

``````Input: grid = [[1,1],[1,2]], r0 = 0, c0 = 0, color = 3
Output: [[3, 3], [3, 2]]
``````

Example 2:

``````Input: grid = [[1,2,2],[2,3,2]], r0 = 0, c0 = 1, color = 3
Output: [[1, 3, 3], [2, 3, 3]]
``````

Example 3:

``````Input: grid = [[1,1,1],[1,1,1],[1,1,1]], r0 = 1, c0 = 1, color = 2
Output: [[2, 2, 2], [2, 1, 2], [2, 2, 2]]
``````

Note:

1. `1 <= grid.length <= 50`
2. `1 <= grid[0].length <= 50`
3. `1 <= grid[i][j] <= 1000`
4. `0 <= r0 < grid.length`
5. `0 <= c0 < grid[0].length`
6. `1 <= color <= 1000`

``````class Solution {
public:
vector<vector<int>> colorBorder(vector<vector<int>>& grid, int r0, int c0, int color) {
if (grid[r0][c0] == color) return grid;
int m = grid.size(), n = grid[0].size(), oldColor = grid[r0][c0];
vector<vector<int>> dirs{{-1, 0}, {0, 1}, {1, 0}, {0, -1}}, border;
set<vector<int>> visited;
queue<vector<int>> q;
q.push({r0, c0});
visited.insert({r0, c0});
while (!q.empty()) {
auto t = q.front(); q.pop();
if (t[0] == 0 || t[0] == m - 1 || t[1] == 0 || t[1] == n - 1) grid[t[0]][t[1]] = color;
for (auto &dir : dirs) {
int x = t[0] + dir[0], y = t[1] + dir[1];
if (x < 0 || x >= m || y < 0 || y >= n || visited.count({x, y})) continue;
if (grid[x][y] == oldColor) {
visited.insert({x, y});
q.push({x, y});
} else {
grid[t[0]][t[1]] = color;
}
}
}
return grid;
}
};
``````

``````class Solution {
public:
vector<vector<int>> colorBorder(vector<vector<int>>& grid, int r0, int c0, int color) {
helper(grid, r0, c0, grid[r0][c0]);
for (int i = 0; i < grid.size(); ++i) {
for (int j = 0; j < grid[0].size(); ++j) {
if (grid[i][j] < 0) grid[i][j] = color;
}
}
return grid;
}
void helper(vector<vector<int>>& grid, int x, int y, int c) {
int m = grid.size(), n = grid[0].size();
if (x < 0 || x >= m || y < 0 || y >= n || grid[x][y] != c) return;
grid[x][y] = -c;
helper(grid, x - 1, y, c);
helper(grid, x + 1, y, c);
helper(grid, x, y - 1, c);
helper(grid, x, y + 1, c);
if (x > 0 && x < m - 1 && y > 0 && y < n - 1 && c == abs(grid[x - 1][y]) && c == abs(grid[x + 1][y]) && c == abs(grid[x][y - 1]) && c == abs(grid[x][y + 1])) {
grid[x][y] = c;
}
}
};
``````

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1034

Island Perimeter

https://leetcode.com/problems/coloring-a-border/

https://leetcode.com/problems/coloring-a-border/discuss/282847/C%2B%2B-with-picture-DFS

https://leetcode.com/problems/coloring-a-border/discuss/283262/JavaPython-3-BFS-and-DFS-codes

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation