Medium

题目描述

给你一个 m x n 的整数矩阵 grid ，以及三个整数 row、col 和 color 。格子中的每个值表示该位置处的网格块的颜色。

如果两个方块在任意 4 个方向上相邻，则称它们是相邻的。

如果两个方块具有相同的颜色且相邻，它们就属于同一个连通分量。

连通分量的边界是指连通分量中满足下述条件之一的所有网格块：

  • 在上、下、左、右任意一个方向上与不属于同一连通分量的网格块相邻
  • 在网格的边界上（第一行/列或最后一行/列）

请你使用指定颜色 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

解题思路

这道题需要找到包含指定位置的连通分量，并为该连通分量的边界着色。

解题思路：

  1. DFS遍历连通分量：从给定位置 (row, col) 开始，使用深度优先搜索遍历所有相同颜色且相邻的网格块，找到完整的连通分量。

  2. 识别边界：在遍历过程中，对于连通分量中的每个网格块，判断它是否为边界：

    • 位于网格边界上（第一行/列或最后一行/列）
    • 至少有一个相邻的网格块不属于同一连通分量（颜色不同或已越界）

  3. 着色策略：只对边界网格块进行着色，内部网格块保持原色。

算法步骤：

  1. 使用DFS遍历连通分量，将所有属于该分量的位置记录下来
  2. 对于每个记录的位置，检查其四个方向的邻居
  3. 如果某个位置在网格边界上，或者至少有一个邻居不属于同一连通分量，则将其标记为边界
  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();
        int originalColor = grid[row][col];
        vector<vector<bool>> visited(m, vector<bool>(n, false));
        vector<pair<int, int>> component;
        
        // DFS to find all cells in the connected component
        dfs(grid, row, col, originalColor, visited, component);
        
        // Check each cell in the component to see if it's on the border
        for (auto& [r, c] : component) {
            if (isBorder(grid, r, c, originalColor)) {
                grid[r][c] = color;
            }
        }
        
        return grid;
    }
    
private:
    void dfs(vector<vector<int>>& grid, int r, int c, int originalColor, 
             vector<vector<bool>>& visited, vector<pair<int, int>>& component) {
        int m = grid.size(), n = grid[0].size();
        if (r < 0 || r >= m || c < 0 || c >= n || visited[r][c] || grid[r][c] != originalColor) {
            return;
        }
        
        visited[r][c] = true;
        component.push_back({r, c});
        
        int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        for (auto& dir : dirs) {
            dfs(grid, r + dir[0], c + dir[1], originalColor, visited, component);
        }
    }
    
    bool isBorder(vector<vector<int>>& grid, int r, int c, int originalColor) {
        int m = grid.size(), n = grid[0].size();
        
        // Check if on the boundary of the grid
        if (r == 0 || r == m - 1 || c == 0 || c == n - 1) {
            return true;
        }
        
        // Check if adjacent to a cell with different color
        int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        for (auto& dir : dirs) {
            int nr = r + dir[0], nc = c + dir[1];
            if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] != originalColor) {
                return true;
            }
        }
        
        return false;
    }
};

class Solution:
    def colorBorder(self, grid: List[List[int]], row: int, col: int, color: int) -> List[List[int]]:
        m, n = len(grid), len(grid[0])
        original_color = grid[row][col]
        visited = [[False] * n for _ in range(m)]
        component = []
        
        def dfs(r, c):
            if (r < 0 or r >= m or c < 0 or c >= n or 
                visited[r][c] or grid[r][c] != original_color):
                return
            
            visited[r][c] = True
            component.append((r, c))
            
            for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                dfs(r + dr, c + dc)
        
        def is_border(r, c):
            # Check if on the boundary of the grid
            if r == 0 or r == m - 1 or c == 0 or c == n - 1:
                return True
            
            # Check if adjacent to a cell with different color
            for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                nr, nc = r + dr, c + dc
                if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] != original_color:
                    return True
            
            return False
        
        # Find all cells in the connected component
        dfs(row, col)
        
        # Color the border cells
        for r, c in component:
            if is_border(r, c):
                grid[r][c] = color
        
        return grid

public class Solution {
    public int[][] ColorBorder(int[][] grid, int row, int col, int color) {
        int m = grid.Length, n = grid[0].Length;
        int originalColor = grid[row][col];
        bool[,] visited = new bool[m, n];
        List<(int, int)> component = new List<(int, int)>();
        
        DFS(grid, row, col, originalColor, visited, component);
        
        foreach (var (r, c) in component) {
            if (IsBorder(grid, r, c, originalColor)) {
                grid[r][c] = color;
            }
        }
        
        return grid;
    }
    
    private void DFS(int[][] grid, int r, int c, int originalColor, 
                     bool[,] visited, List<(int, int)> component) {
        int m = grid.Length, n = grid[0].Length;
        if (r < 0 || r >= m || c < 0 || c >= n || visited[r, c] || grid[r][c] != originalColor) {
            return;
        }
        
        visited[r, c] = true;
        component.Add((r, c));
        
        int[,] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        for (int i = 0; i < 4; i++) {
            DFS(grid, r + dirs[i, 0], c + dirs[i, 1], originalColor, visited, component);
        }
    }
    
    private bool IsBorder(int[][] grid, int r, int c, int originalColor) {
        int m = grid.Length, n = grid[0].Length;
        
        // Check if on the boundary of the grid
        if (r == 0 || r == m - 1 || c == 0 || c == n - 1) {
            return true;
        }
        
        // Check if adjacent to a cell with different color
        int[,] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        for (int i = 0; i < 4; i++) {
            int nr = r + dirs[i, 0], nc = c + dirs[i, 1];
            if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] != originalColor) {
                return true;
            }
        }
        
        return false;
    }
}

var colorBorder = function(grid, row, col, color) {
    const m = grid.length;
    const n = grid[0].length;
    const originalColor = grid[row][col];
    const visited = Array(m).fill().map(() => Array(n).fill(false));
    const component = [];
    
    function dfs(r, c) {
        if (r < 0 || r >= m || c < 0 || c >= n || visited[r][c] || grid[r][c] !== originalColor) {
            return;
        }
        
        visited[r][c] = true;
        component.push([r, c]);
        
        dfs(r + 1, c);
        dfs(r - 1, c);
        dfs(r, c + 1);
        dfs(r, c - 1);
    }
    
    function isBorder(r, c) {
        if (r === 0 || r === m - 1 || c === 0 || c === n - 1) {
            return true;
        }
        
        const directions = [[0, 1], [0, -1], [1, 0], [-1, 0]];
        for (let [dr, dc] of directions) {
            const nr = r + dr;
            const nc = c + dc;
            if (grid[nr][nc] !== originalColor) {
                return true;
            }
        }
        return false;
    }
    
    dfs(row, col);
    
    for (let [r, c] of component) {
        if (isBorder(r, c)) {
            grid[r][c] = color;
        }
    }
    
    return grid;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(m × n) - 最坏情况下需要遍历整个网格来找到连通分量，每个位置最多访问一次
空间复杂度O(m × n) - 需要visited数组记录访问状态，以及递归调用栈和component列表的空间

相关题目