原文链接: https://leetcode-cn.com/problems/coloring-a-border

英文原文

You are given an m x n integer matrix grid, and three integers row, col, and color. Each value in the grid represents the color of the grid square at that location.

Two squares belong to the same connected component 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).

You should color the border of the connected component that contains the square grid[row][col] with color.

Return the final grid.

 

Example 1:

Input: grid = [[1,1],[1,2]], row = 0, col = 0, color = 3
Output: [[3,3],[3,2]]

Example 2:

Input: grid = [[1,2,2],[2,3,2]], row = 0, col = 1, color = 3
Output: [[1,3,3],[2,3,3]]

Example 3:

Input: grid = [[1,1,1],[1,1,1],[1,1,1]], row = 1, col = 1, color = 2
Output: [[2,2,2],[2,1,2],[2,2,2]]

 

Constraints:

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 50
• 1 <= grid[i][j], color <= 1000
• 0 <= row < m
• 0 <= col < n

中文题目

给你一个大小为 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

 

通过代码

高赞题解

题意

DFS

class Solution {
private:
    void dfs(vector<vector<int>>& grid, int r, int c, int firstColor) {
        if (r < 0 || r >= grid.size() || c < 0 || c >= grid[0].size() || grid[r][c] != firstColor) {
            return;
        }
        grid[r][c] = -firstColor;   // 标记方格颜色为相反数，表示已经访问过
        dfs(grid, r - 1, c, firstColor);
        dfs(grid, r + 1, c, firstColor);
        dfs(grid, r, c - 1, firstColor);
        dfs(grid, r, c + 1, firstColor);
        // dfs搜索结束之后，判断本单元格是否属于连通分量内部，如果是就将颜色反转为正数
        if (r > 0 && r < grid.size() - 1 && c > 0 && c < grid[0].size() - 1 &&
        firstColor == abs(grid[r - 1][c]) && firstColor == abs(grid[r + 1][c]) &&
        firstColor == abs(grid[r][c - 1]) && firstColor == abs(grid[r][c + 1])) {
            grid[r][c] = firstColor;
        }
    }
public:
    vector<vector<int>> colorBorder(vector<vector<int>>& grid, int r0, int c0, int color) {
        dfs(grid, r0, c0, grid[r0][c0]);
        for (int i = 0; i < grid.size(); ++i) {
            for (int j = 0; j < grid[0].size(); ++j) {
                // 至此，单元格值为负数的都是连通分量的边界，颜色调整为 color
                grid[i][j] = grid[i][j] < 0 ? color : grid[i][j];
            }
        }
        return grid;
    }
};

统计信息

通过次数	提交次数	AC比率
4853	11060	43.9%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言

相似题目

题目	难度
岛屿的周长	简单