Hard

题目描述

有一台奇怪的打印机有以下两个特殊要求：

  • 每一次操作时，打印机会用一种颜色打印一个矩形的形状，覆盖矩形对应格子里原来的颜色。
  • 一旦打印机使用了一种颜色，那么相同的颜色不能再被使用。

给你一个 m x n 的矩阵 targetGrid，其中 targetGrid[row][col] 是位置 (row, col) 的颜色。

如果能够按照上述规则打印出矩阵 targetGrid，请返回 true，否则返回 false。

示例 1:

输入：targetGrid = [[1,1,1,1],[1,2,2,1],[1,2,2,1],[1,1,1,1]]
输出：true

示例 2:

输入：targetGrid = [[1,1,1,1],[1,1,3,3],[1,1,3,4],[5,5,1,4]]
输出：true

示例 3:

输入：targetGrid = [[1,2,1],[2,1,2],[1,2,1]]
输出：false
解释：无法得到 targetGrid，因为无法在不同的时间里使用相同的颜色。

提示：

  • m == targetGrid.length
  • n == targetGrid[i].length
  • 1 <= m, n <= 60
  • 1 <= targetGrid[row][col] <= 60

解题思路

这道题需要判断给定的矩阵是否可以通过特殊打印机的规则生成。关键在于理解打印规则：每次只能打印一个矩形区域的单一颜色，且每种颜色只能使用一次。

核心思路：拓扑排序

我们可以从反向思考：如果一个颜色能够被最后打印，那么它在最终矩阵中的所有位置必须能够形成一个矩形区域，且该区域内不能有其他颜色。

具体步骤：

  1. 找到每种颜色的边界矩形：对于每种颜色，找出它在矩阵中出现的最小边界矩形
  2. 构建依赖图：如果颜色A的边界矩形包含了颜色B的某些位置，说明A必须在B之前打印，建立A→B的有向边
  3. 拓扑排序验证：通过拓扑排序检查是否存在环，如果无环则可以找到合法的打印顺序

算法流程：

  • 遍历矩阵，记录每种颜色的边界
  • 对每种颜色，检查其边界矩形内是否包含其他颜色，建立依赖关系
  • 使用拓扑排序（基于入度的BFS）验证是否可以完成所有颜色的打印

代码实现

class Solution {
public:
    bool isPrintable(vector<vector<int>>& targetGrid) {
        int m = targetGrid.size(), n = targetGrid[0].size();
        
        // 记录每种颜色的边界
        unordered_map<int, vector<int>> bounds; // color -> {minR, maxR, minC, maxC}
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int color = targetGrid[i][j];
                if (bounds.find(color) == bounds.end()) {
                    bounds[color] = {i, i, j, j};
                } else {
                    bounds[color][0] = min(bounds[color][0], i);
                    bounds[color][1] = max(bounds[color][1], i);
                    bounds[color][2] = min(bounds[color][2], j);
                    bounds[color][3] = max(bounds[color][3], j);
                }
            }
        }
        
        // 构建依赖图
        unordered_map<int, unordered_set<int>> graph;
        unordered_map<int, int> indegree;
        for (auto& [color, _] : bounds) {
            graph[color] = unordered_set<int>();
            indegree[color] = 0;
        }
        
        for (auto& [color, bound] : bounds) {
            int minR = bound[0], maxR = bound[1], minC = bound[2], maxC = bound[3];
            for (int i = minR; i <= maxR; i++) {
                for (int j = minC; j <= maxC; j++) {
                    int curColor = targetGrid[i][j];
                    if (curColor != color && graph[color].find(curColor) == graph[color].end()) {
                        graph[color].insert(curColor);
                        indegree[curColor]++;
                    }
                }
            }
        }
        
        // 拓扑排序
        queue<int> q;
        for (auto& [color, deg] : indegree) {
            if (deg == 0) q.push(color);
        }
        
        int processed = 0;
        while (!q.empty()) {
            int color = q.front();
            q.pop();
            processed++;
            
            for (int nextColor : graph[color]) {
                indegree[nextColor]--;
                if (indegree[nextColor] == 0) {
                    q.push(nextColor);
                }
            }
        }
        
        return processed == bounds.size();
    }
};

class Solution:
    def isPrintable(self, targetGrid: List[List[int]]) -> bool:
        from collections import defaultdict, deque
        
        m, n = len(targetGrid), len(targetGrid[0])
        
        # 记录每种颜色的边界
        bounds = {}
        for i in range(m):
            for j in range(n):
                color = targetGrid[i][j]
                if color not in bounds:
                    bounds[color] = [i, i, j, j]
                else:
                    bounds[color][0] = min(bounds[color][0], i)
                    bounds[color][1] = max(bounds[color][1], i)
                    bounds[color][2] = min(bounds[color][2], j)
                    bounds[color][3] = max(bounds[color][3], j)
        
        # 构建依赖图
        graph = defaultdict(set)
        indegree = defaultdict(int)
        
        for color in bounds:
            indegree[color] = 0
        
        for color, (minR, maxR, minC, maxC) in bounds.items():
            for i in range(minR, maxR + 1):
                for j in range(minC, maxC + 1):
                    curColor = targetGrid[i][j]
                    if curColor != color and curColor not in graph[color]:
                        graph[color].add(curColor)
                        indegree[curColor] += 1
        
        # 拓扑排序
        queue = deque([color for color, deg in indegree.items() if deg == 0])
        processed = 0
        
        while queue:
            color = queue.popleft()
            processed += 1
            
            for nextColor in graph[color]:
                indegree[nextColor] -= 1
                if indegree[nextColor] == 0:
                    queue.append(nextColor)
        
        return processed == len(bounds)

public class Solution {
    public bool IsPrintable(int[][] targetGrid) {
        int m = targetGrid.Length, n = targetGrid[0].Length;
        
        // 记录每种颜色的边界
        var bounds = new Dictionary<int, int[]>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int color = targetGrid[i][j];
                if (!bounds.ContainsKey(color)) {
                    bounds[color] = new int[]{i, i, j, j};
                } else {
                    bounds[color][0] = Math.Min(bounds[color][0], i);
                    bounds[color][1] = Math.Max(bounds[color][1], i);
                    bounds[color][2] = Math.Min(bounds[color][2], j);
                    bounds[color][3] = Math.Max(bounds[color][3], j);
                }
            }
        }
        
        // 构建依赖图
        var graph = new Dictionary<int, HashSet<int>>();
        var indegree = new Dictionary<int, int>();
        
        foreach (var color in bounds.Keys) {
            graph[color] = new HashSet<int>();
            indegree[color] = 0;
        }
        
        foreach (var kvp in bounds) {
            int color = kvp.Key;
            int[] bound = kvp.Value;
            int minR = bound[0], maxR = bound[1], minC = bound[2], maxC = bound[3];
            
            for (int i = minR; i <= maxR; i++) {
                for (int j = minC; j <= maxC; j++) {
                    int curColor = targetGrid[i][j];
                    if (curColor != color && !graph[color].Contains(curColor)) {
                        graph[color].Add(curColor);
                        indegree[curColor]++;
                    }
                }
            }
        }
        
        // 拓扑排序
        var queue = new Queue<int>();
        foreach (var kvp in indegree) {
            if (kvp.Value == 0) queue.Enqueue(kvp.Key);
        }
        
        int processed = 0;
        while (queue.Count > 0) {
            int color = queue.Dequeue();
            processed++;
            
            foreach (int nextColor in graph[color]) {
                indegree[nextColor]--;
                if (indegree[nextColor] == 0) {
                    queue.Enqueue(nextColor);
                }
            }
        }
        
        return processed == bounds.Count;
    }
}

var isPrintable = function(targetGrid) {
    const m = targetGrid.length;
    const n = targetGrid[0].length;
    
    // Find bounding rectangle for each color
    const bounds = new Map();
    
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            const color = targetGrid[i][j];
            if (!bounds.has(color)) {
                bounds.set(color, {minR: i, maxR: i, minC: j, maxC: j});
            } else {
                const bound = bounds.get(color);
                bound.minR = Math.min(bound.minR, i);
                bound.maxR = Math.max(bound.maxR, i);
                bound.minC = Math.min(bound.minC, j);
                bound.maxC = Math.max(bound.maxC, j);
            }
        }
    }
    
    // Build dependency graph
    const graph = new Map();
    const colors = Array.from(bounds.keys());
    
    for (const color of colors) {
        graph.set(color, new Set());
    }
    
    for (const color of colors) {
        const bound = bounds.get(color);
        const dependencies = new Set();
        
        // Check all cells in the bounding rectangle
        for (let i = bound.minR; i <= bound.maxR; i++) {
            for (let j = bound.minC; j <= bound.maxC; j++) {
                if (targetGrid[i][j] !== color) {
                    dependencies.add(targetGrid[i][j]);
                }
            }
        }
        
        graph.set(color, dependencies);
    }
    
    // Topological sort using DFS
    const visited = new Set();
    const recStack = new Set();
    
    function dfs(color) {
        if (recStack.has(color)) return false; // Cycle detected
        if (visited.has(color)) return true;
        
        visited.add(color);
        recStack.add(color);
        
        for (const dep of graph.get(color)) {
            if (!dfs(dep)) return false;
        }
        
        recStack.delete(color);
        return true;
    }
    
    for (const color of colors) {
        if (!visited.has(color)) {
            if (!dfs(color)) return false;
        }
    }
    
    return true;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(mn × k)
空间复杂度O(k²)

其中 m、n 分别为矩阵的行数和列数，k 为不同颜色的数量。时间复杂度主要来自于构建依赖图时需要检查每种颜色边界矩形内的所有位置，空间复杂度主要用于存储依赖图。

相关题目