Problem

There is a strange printer with the following two special requirements:

  • On each turn, the printer will print a solid rectangular pattern of a single color on the grid. This will cover up the existing colors in the rectangle.
  • Once the printer has used a color for the above operation, the same color cannot be used again.

You are given a m x n matrix targetGrid, where targetGrid[row][col] is the color in the position (row, col) of the grid.

Return true if it is possible to print the matrix targetGrid, otherwise, return false.

https://leetcode.com/problems/strange-printer-ii/

Example 1:

case1

Input: targetGrid = [[1,1,1,1],[1,2,2,1],[1,2,2,1],[1,1,1,1]]
Output: true

Example 2:

case2

Input: targetGrid = [[1,1,1,1],[1,1,3,3],[1,1,3,4],[5,5,1,4]]
Output: true

Example 3:

Input: targetGrid = [[1,2,1],[2,1,2],[1,2,1]]
Output: false
Explanation: It is impossible to form targetGrid because it is not allowed to print the same color in different turns.

Constraints:

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

Test Cases

1
2
class Solution:
    def isPrintable(self, targetGrid: List[List[int]]) -> bool:
solution_test.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import pytest

from solution import Solution
from solution2 import Solution as Solution2
from solution3 import Solution as Solution3


@pytest.mark.parametrize('targetGrid, expected', [
    ([[1,1,1,1],[1,2,2,1],[1,2,2,1],[1,1,1,1]], True),
    ([[1,1,1,1],[1,1,3,3],[1,1,3,4],[5,5,1,4]], True),
    ([[1,2,1],[2,1,2],[1,2,1]], False),
])
@pytest.mark.parametrize('sol', [Solution(), Solution2(), Solution3()])
def test_solution(sol, targetGrid, expected):
    assert sol.isPrintable(targetGrid.copy()) == expected

Thoughts

跟 664. Strange Printer 似乎没有太大关联，除了都是「打印机」。

对于任何一个颜色，找到能围住所有该颜色格子的最小矩形区域，在打印该颜色的时候，这个区域是最小的需要打印的范围。如果这个区域内有其他的颜色，那么那些颜色就都要在之后再打印。

作一个有向图，顶点是所有的颜色。如果颜色 v 需要在颜色 u 之后打印，就画一条 u 到 v 的有向边。检查图中是否存在环，存在则无法成功打印。

判定图中是否有环可以参考 207. Course Schedule，采用的方法是任取一个节点，从它出发做深度遍历，如果当前路径上的节点被再次访问到，说明有环。

另外一种方式是在图中找任意一个入度为 0 的点，将其及其相连的边都删除（它的后继节点的入度减一）。持续操作，如果最后剩下若干个节点，入度均大于 0，就说明有环。

整体很慢啊，设一共有 k 个颜色，构造图的时间是 O(m * n * k)，判断是否有环的时间是 O(k²)。

Code

solution.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
from collections import defaultdict


min2 = lambda a, b: a if a <= b else b
max2 = lambda a, b: a if a >= b else b


class Rect:
    def __init__(self, row: int, col: int) -> None:
        self.top = self.bottom = row
        self.left = self.right = col

    def extend(self, row: int, col: int) -> None:
        # self.top = min2(self.top, row)
        self.bottom = max2(self.bottom, row)
        self.left = min2(self.left, col)
        self.right = max2(self.right, col)

    def contains(self, row: int, col: int) -> bool:
        return self.top <= row <= self.bottom and self.left <= col <= self.right


def has_circle(graph: dict[int, set[int]]) -> bool:
    nodes = {u: False for u in graph} # False: not processed; True: processing; <Removed>: finished.
    while nodes:
        stack = [next(iter(nodes))]
        while stack:
            u = stack.pop()
            if u not in nodes: # `u` is already finished.
                continue
            elif nodes[u]: # `u` is under processing, then finish it.
                nodes.pop(u)
                continue

            nodes[u] = True # `u` is not processed, mark it processing.
            stack.append(u)
            for v in graph[u]:
                if v in nodes:
                    if nodes[v]: # If `v` is under processing, there is a circle.
                        return True
                    stack.append(v) # `v` is not processed (and not finished).

    return False


def has_circle2(graph: dict[int, set[int]]) -> bool:
    in_degrees = defaultdict(int, {u: 0 for u in graph}) # u: u's in-degree.
    for u in graph:
        for v in graph[u]:
            in_degrees[v] += 1

    while in_degrees:
        zero = next((u for u, d in in_degrees.items() if d == 0), None)
        if zero is None:
            return True

        in_degrees.pop(zero)
        for v in graph[zero]:
            if v in in_degrees:
                in_degrees[v] -= 1

    return False


class Solution:
    def isPrintable(self, targetGrid: list[list[int]]) -> bool:
        m = len(targetGrid)
        n = len(targetGrid[0])

        # Get surrounding boxes for each color.
        boxes: dict[int, Rect] = {} # {color: surrounding rectangle}
        for i in range(m):
            for j in range(n):
                c = targetGrid[i][j]
                if c not in boxes:
                    boxes[c] = Rect(i, j)
                else:
                    boxes[c].extend(i, j)

        # Build a dependency graph.
        graph: dict[int, set[int]] = defaultdict(set) # {color: other colors should print later}
        # graph = {c: set() for c in boxes}
        for i in range(m):
            for j in range(n):
                c = targetGrid[i][j]
                for c2, box in boxes.items():
                    if c2 != c and box.contains(i, j):
                        graph[c2].add(c)

        return not has_circle(graph)

Faster

更直接的方式是先找需要最后打印的颜色。显然如果一个颜色的包围矩形内每个格子都是这个颜色，那么它应该最后被打印。

一种方式是记录每个颜色占用的格子数量，判断此数量是否与包围矩形的面积相等。另一种方式是直接扫描包围矩形中的所有格子，检查每个格子的颜色。

确定了可以最后打印的颜色之后，它原本占用的那些格子在打印该颜色之前是可以随意打印的。

一种方式是对于该颜色的每一个格子，所有包含该格子的其他颜色的包围矩形，需要打印的面积减一（或者让另外那种颜色的格子数量加一）。另一种方式是将该格子标记为镂空（比如将颜色设置为 0），一个包围矩形中镂空的格子对是否可打印没有影响。

这样不断寻找可以后打印的颜色，如果最后剩下几个颜色，哪一个都无法（在这几个颜色的）最后打印，就说明整个 targetGrid 无法打印。

最坏情况时间复杂度都是 O(m * n * k²)。

solution2.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
from collections import defaultdict


min2 = lambda a, b: a if a <= b else b
max2 = lambda a, b: a if a >= b else b


class Rect:
    def __init__(self, row: int, col: int) -> None:
        self.top = self.bottom = row
        self.left = self.right = col
        self.area = 1

    def extend(self, row: int, col: int) -> None:
        if self.contains(row, col): return
        # self.top = min2(self.top, row)
        self.bottom = max2(self.bottom, row)
        self.left = min2(self.left, col)
        self.right = max2(self.right, col)
        self.area = (self.bottom - self.top + 1) * (self.right - self.left + 1)

    def contains(self, row: int, col: int) -> bool:
        return self.top <= row <= self.bottom and self.left <= col <= self.right


class Solution:
    def isPrintable(self, targetGrid: list[list[int]]) -> bool:
        m = len(targetGrid)
        n = len(targetGrid[0])
        boxes: dict[int, Rect] = {} # {color: surrounding rectangle}
        counts: dict[int, int] = defaultdict(int) # {color: number of cells can be printed to this color}
        for i in range(m):
            for j in range(n):
                color = targetGrid[i][j]
                counts[color] += 1
                if color not in boxes:
                    boxes[color] = Rect(i, j)
                else:
                    boxes[color].extend(i, j)

        while counts:
            color = next((c for c, cnt in counts.items() if cnt == boxes[c].area), None)
            if color is None:
                return False

            box = boxes[color]
            for i in range(box.top, box.bottom + 1):
                for j in range(box.left, box.right + 1):
                    if targetGrid[i][j] != color: continue
                    for c2 in counts:
                        box2 = boxes[c2]
                        if c2 != color and box2.contains(i, j):
                            counts[c2] += 1

            counts.pop(color)

        return True
solution3.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
from itertools import product
from typing import Iterable


min2 = lambda a, b: a if a <= b else b
max2 = lambda a, b: a if a >= b else b


class Rect:
    def __init__(self, row: int, col: int) -> None:
        self.top = self.bottom = row
        self.left = self.right = col

    def extend(self, row: int, col: int) -> None:
        # self.top = min2(self.top, row)
        self.bottom = max2(self.bottom, row)
        self.left = min2(self.left, col)
        self.right = max2(self.right, col)

    def __iter__(self) -> Iterable[tuple[int, int]]:
        yield from product(range(self.top, self.bottom+1), range(self.left, self.right+1))


class Solution:
    def isPrintable(self, targetGrid: list[list[int]]) -> bool:
        m = len(targetGrid)
        n = len(targetGrid[0])
        boxes: dict[int, Rect] = {} # {color: surrounding rectangle}
        for i, j in product(range(m), range(n)):
            color = targetGrid[i][j]
            if color not in boxes:
                boxes[color] = Rect(i, j)
            else:
                boxes[color].extend(i, j)

        def printable(color: int) -> bool:
            box = boxes[color]

            for i, j in box:
                if targetGrid[i][j] != color and targetGrid[i][j] > 0:
                    return False

            for i, j in box:
                targetGrid[i][j] = 0

            return True

        colors = set(boxes)
        while colors:
            printed = set(filter(printable, colors))
            if not printed: return False
            colors -= printed

        return True

实际提交之后的运行时间，solution.py > solution2.py > solution3.py（基本都是差 3 倍），但时间复杂度都差不多。尤其 solution2 和 solution3 哪个跑得快，跟测试用例的情况也有较大关系。

hard
参考资料
许可协议

本文除了题目描述（Problem）部分之外，其他内容由 Calf 原创，采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。

分享文章

快来参与讨论吧~