解題說明
Strange Printer II
題目描述： 有一個 m × n 的目標網格 targetGrid，一台特殊印表機每次可以列印一個實心矩形（所有格子填同一個顏色），後列印的顏色會覆蓋先列印的顏色。判斷是否存在一種列印順序能得到目標網格。
解題思路： 對每個顏色，找出它在網格中出現的最小包圍矩形（bounding box）。在這個矩形內，所有不是該顏色的格子必然是在這個顏色之後列印的。因此，建立一個有向圖：如果顏色 A 的包圍矩形內出現了顏色 B，則 A 必須在 B 之前列印（A -> B）。如果這個圖存在拓撲排序（無環），則可以列印出目標網格。
C++ 解法
複雜度分析
時間複雜度：O(m × n × C + C^2) — 其中 C 為顏色數量。對每種顏色掃描其包圍矩形需 O(m × n)，拓撲排序需 O(C + E)
空間複雜度：O(C^2 + m × n) — 圖的鄰接表最多 C^2 條邊
虛擬碼
1. For each color c, find its bounding box (minRow, maxRow, minCol, maxCol) 2. Build directed graph: for each color c, scan its bounding box - If cell (i,j) has a different color d, add edge c -> d (c must print before d) 3. Run topological sort (Kahn's algorithm) on the graph 4. If all colors are processed (no cycle), return true; otherwise return false
其他解法
方法二：DFS 環檢測 使用 DFS 和三色標記（白/灰/黑）來檢測有向圖中是否有環。如果發現灰色節點被再次訪問，則存在環。邏輯等價於 BFS 拓撲排序。
方法三：逐步消除法 反覆找到可以「最後列印」的顏色（其包圍矩形內所有格子要麼是自己的顏色要麼已被消除），將其消除。如果最終所有顏色都被消除則可行。直觀但效率稍低。
延伸思考
- 如果印表機可以列印任意形狀（不只是矩形），問題會如何簡化？
- 如果要求輸出一種有效的列印順序，如何從拓撲排序中得到？
- 這道題與「判斷課程能否全部完成」（LeetCode 207）在結構上有什麼相似之處？