1591. Strange Printer II
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:

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

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.lengthn == targetGrid[i].length1 <= m, n <= 601 <= targetGrid[row][col] <= 60
Test Cases
class Solution:
def isPrintable(self, targetGrid: List[List[int]]) -> bool: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
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²)。
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
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 哪个跑得快,跟测试用例的情况也有较大关系。
评论需要 JavaScript。