[LeetCode] 1034. Coloring A Border

[grandyang]

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

这道题给了一个二维数组 grid，和一个起始位置 (r0, c0)，格子里的数字代表不同的颜色，又给了一个新的颜色 color，现在让给起始位置所在的连通区域的边缘填充这种新的颜色。这立马让博主想到了 Flash 中的墨水瓶工具，就是给图形的边缘上色的。说到 Flash 动画软件，博主高中的时候特别痴迷于制作 Flash 动画（感觉暴露年龄了），直接影响了博主大学的专业选择，义无反顾的投入了 Computer Science 这一行业。但是去年年底 Adobe 公司已经彻底判了 Flash （已经改名叫了 Animation）的死刑，爷青结！扯远了，拉回来，这道题的难点就是如何找出连通区域的边缘，找连通区域并不难，因为有了起始点，可以用 DFS 或者 BFS 来找出所有相连的位置，而边缘位置需要进一步判断，一种情况是当前位置是二维矩阵的边缘，那么其一定也是连通区域的边缘，另一种情况是若四个相邻位置有其他的颜色，则当前位置也一定是边缘。下面先来看 BFS 的解法，主体还是经典的 BFS 写法不变，使用队列 queue，和一个 TreeSet 来记录已经遍历过的位置。将起始位置先放入 queue 和 visited 集合，然后进行 while 循环，取出队首元素，然后判断当前位置是否是二维数组的边缘，是的话直接将颜色更新 color。然后遍历周围四个位置，若越界了或者访问过了直接跳过，然后看若颜色和起始位置的颜色相同，则加入 visited 和 queue，否则将当前位置的颜色更新为 color，因为周围有不同的颜色了，参见代码如下：

解法一：

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;
    }
};

下面来看 DFS 的写法，整个思路还是一样的，首先调用一个递归函数，目的是将连通区域的边缘先标记为原来的数字的相反数，然后之后再遍历一遍数组，找出负数，并更新为 color 即可。在递归函数中，先判断是否越界，或者不是起始颜色的位置，直接返回。否则将当前位置更新为相反数，然后对周围四个位置调用递归函数，之后还需要判断当前位置是否是边缘，不是边缘的话，要还原为正数。判断方法就是看周围四个位置的数字的绝对值是否等于起始位置的数字，参见代码如下：

解法二：

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 同步地址:

#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 题目讲解汇总(持续更新中...)