Strange Printer II (LeetCode 1591)
Đề bài
LeetCode 1591 – Strange Printer II (Máy in kỳ lạ II) – độ khó Hard.
Có một máy in kỳ lạ với hai yêu cầu đặc biệt sau:
- Mỗi lượt, máy in sẽ in một hình chữ nhật đặc tô một màu duy nhất lên lưới. Màu mới sẽ đè lên các màu đang có trong hình chữ nhật đó.
- Khi máy in đã dùng một màu cho thao tác trên, màu đó không được dùng lại nữa.
Cho ma trận targetGrid kích thước m x n, trong đó targetGrid[row][col] là màu tại vị trí (row, col) của lưới.
Yêu cầu: trả về true nếu có thể in ra được ma trận targetGrid, ngược lại trả về false.
Ràng buộc:
m == targetGrid.lengthn == targetGrid[i].length- $1 \le m, n \le 60$
- $1 \le$
targetGrid[row][col]$\le 60$
Ví dụ 1:
Input: targetGrid = [[1,1,1,1],[1,2,2,1],[1,2,2,1],[1,1,1,1]]
Output: trueVí dụ 2:
Input: targetGrid = [[1,1,1,1],[1,1,3,3],[1,1,3,4],[5,5,1,4]]
Output: trueVí dụ 3:
Input: targetGrid = [[1,2,1],[2,1,2],[1,2,1]]
Output: falseGiải thích: không thể tạo ra targetGrid vì không được phép in cùng một màu ở các lượt khác nhau.
Ví dụ 4:
Input: targetGrid = [[1,1,1],[3,1,3]]
Output: false1591. Strange Printer II – Hard
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.
Example 1: (see the first picture in the Vietnamese tab)
Input: targetGrid = [[1,1,1,1],[1,2,2,1],[1,2,2,1],[1,1,1,1]]
Output: trueExample 2: (see the second picture in the Vietnamese tab)
Input: targetGrid = [[1,1,1,1],[1,1,3,3],[1,1,3,4],[5,5,1,4]]
Output: trueExample 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.Example 4:
Input: targetGrid = [[1,1,1],[3,1,3]]
Output: falseConstraints:
m == targetGrid.lengthn == targetGrid[i].length1 <= m, n <= 601 <= targetGrid[row][col] <= 60
Lời mở đầu
Bài này mình được một bạn học viên hỏi nên sẵn tiện mình viết bài giải chi tiết để nhiều bạn được tham khảo luôn. Hy vọng mang đến được giá trị cho các bạn 😇.
class Solution. Để các bạn chạy thử được trên máy (hoặc trang Chạy code online), mọi code trong bài đều có thêm hàm main đọc từ bàn phím theo định dạng: dòng đầu là hai số $m$ (số hàng) và $n$ (số cột), tiếp theo là $m$ dòng, mỗi dòng $n$ số của targetGrid; in ra true hoặc false. Ví dụ 4 của đề viết thành:
2 3
1 1 1
3 1 3false.Tóm tắt đề bài: bạn được cho một bảng số $a$ gồm $N \times M$ số. Máy in sẽ lựa chọn một hình chữ nhật con trong bảng và in vào hình chữ nhật đó một con số bất kỳ (màu), đè lên những gì đang có. Hai lần in khác nhau sẽ là 2 số in khác nhau. Bạn cần kiểm tra liệu có tồn tại một cách in sao cho sau khi in xong, bảng ban đầu sẽ trở thành bảng chữ nhật đã cho.
Giải thích ví dụ 4 cho bạn nào chưa hiểu đề: màu 3 xuất hiện ở ô $(1, 0)$ và $(1, 2)$, nên hình chữ nhật in màu 3 phải phủ cả ô $(1, 1)$ ở giữa ⇒ sau đó màu 1 phải đè lên ô $(1, 1)$, tức là 1 in sau 3. Nhưng màu 1 lại có mặt ở cả hàng 0 lẫn ô $(1, 1)$, nên hình chữ nhật màu 1 phải phủ cả hàng 1, tức là phủ luôn ô $(1, 0)$ đang mang màu 3 ⇒ 3 in sau 1. Mâu thuẫn ⇒ false. Ví dụ 3 cũng vậy: màu 1 và màu 2 "đòi" in sau nhau.
Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.
Nộp bài trên CLUE OJLộ trình lời giải, bấm vào từng phần để nhảy tới:
Cách 1Dựng đồ thị thứ tự in, DFS kiểm tra chu trình – O(60·N·M)
Bước 1: khung chữ nhật của mỗi màu
Mỗi màu $v$ chỉ được in đúng một lần, bằng một hình chữ nhật. Hình chữ nhật đó phải phủ hết các ô cuối cùng mang màu $v$, nên nó chứa ít nhất khung chữ nhật nhỏ nhất bao các ô màu $v$. Với mỗi giá trị $v$ từ 1 đến 60, ta tìm tọa độ $(x_1, y_1)$ là góc trái trên và $(x_2, y_2)$ là góc phải dưới của khung đó (hàng nhỏ nhất, cột nhỏ nhất, hàng lớn nhất, cột lớn nhất trong các ô có $a[i][j] = v$).
Bước 2: dựng đồ thị "ai in trước ai"
Ta duyệt toàn bộ các phần tử trong khung $(x_1, y_1, x_2, y_2)$ của màu $v$. Nếu giá trị phần tử đó khác $v$, giả sử là giá trị $k$, điều này có nghĩa là sau khi in ra hình chữ nhật có giá trị $v$, máy in sẽ in tiếp một hình chữ nhật có giá trị $k$ đè lên. Do đó ta tạo một cạnh nối giữa $v$ và $k$: $v$ phải in trước $k$.
adj[before].push_back(v) với before là màu nằm trong khung của $v$, nghĩa là "before phải chờ $v$ in trước". Đảo hết chiều các cạnh thì đồ thị có chu trình hay không vẫn y như cũ, nên kết quả không đổi. Các bạn đọc code nhớ để ý chỗ này kẻo rối nhé.Bước 3: DFS tìm chu trình
Ta sử dụng DFS để xác định đồ thị trên có chu trình hay không, dùng mảng state với 3 trạng thái:
state[u] = 0: chưa thăm.state[u] = 1: đang thăm (đỉnh $u$ đang nằm trên đường DFS hiện tại, chưa đi hết các đỉnh kề).state[u] = 2: đã thăm xong.
Khi đang ở $u$ mà đi sang một đỉnh $v$ có state[v] = 1, tức là từ $v$ đi một vòng lại quay về chính $v$ ⇒ có chu trình. Nếu có chu trình, kết quả là false, không có chu trình thì kết quả là true.
Em nhập bảng (các hàng cách nhau bởi dấu ;) rồi bấm Tiếp. Phần đầu xem khung của từng màu (viền cam) và các cạnh được thêm; phần sau xem DFS tô đỉnh vàng (đang thăm), xanh (đã xong) và phát hiện chu trình (cạnh đỏ). Mũi tên $k \to v$ vẽ đúng như mảng adj trong code: $k$ phải chờ $v$ in trước:
Code dưới đây của mình đã AC với tư tưởng đã trình bày ở trên, anh em có thể tham khảo nhé:
#include <bits/stdc++.h>
using namespace std;
vector <int> adj[65];
int state[65];
bool ans = true;
class Solution {
public:
void dfs(int u) {
if (ans == false) {
return;
}
state[u] = 1;
for (int i = 0; i < (int) adj[u].size(); i++) {
int v = adj[u][i];
if (state[v] == 1) {
ans = false;
return;
}
if (state[v] == 0) {
dfs(v);
}
}
state[u] = 2;
}
bool isPrintable(vector<vector<int>>& a) {
int n = (int) a.size();
int m = (int) a[0].size();
for (int v = 1; v <= 60; v++) {
adj[v].clear();
state[v] = 0;
}
for (int v = 1; v <= 60; v++) {
int x1 = 65, y1 = 65, x2 = -1, y2 = -1;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (a[i][j] == v) {
x1 = min(x1, i);
y1 = min(y1, j);
x2 = max(x2, i);
y2 = max(y2, j);
}
}
}
if (x2 != -1 && y2 != -1) {
set <int> S;
for (int i = x1; i <= x2; i++) {
for (int j = y1; j <= y2; j++) {
S.insert(a[i][j]);
}
}
for (set <int> :: iterator it = S.begin(); it != S.end(); it++) {
int before = *it;
if (before != v) {
adj[before].push_back(v);
}
}
}
}
ans = true;
for (int u = 1; u <= 60; u++) {
if (state[u] == 0) {
dfs(u);
}
}
return ans;
}
};
int main() {
int T;
cin >> T;
while (T--) {
int n, m;
cin >> n >> m;
vector<vector<int>> a(n, vector<int>(m));
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++) cin >> a[i][j];
Solution sol;
cout << (sol.isPrintable(a) ? "true" : "false") << "\n";
}
return 0;
}import sys
from typing import List
sys.setrecursionlimit(10000)
class Solution:
def isPrintable(self, a: List[List[int]]) -> bool:
n, m = len(a), len(a[0])
adj = [[] for _ in range(65)]
state = [0] * 65 # 0: chưa thăm, 1: đang thăm, 2: đã xong
for v in range(1, 61):
x1, y1, x2, y2 = 65, 65, -1, -1
for i in range(n):
for j in range(m):
if a[i][j] == v:
x1 = min(x1, i)
y1 = min(y1, j)
x2 = max(x2, i)
y2 = max(y2, j)
if x2 != -1 and y2 != -1:
S = set()
for i in range(x1, x2 + 1):
for j in range(y1, y2 + 1):
S.add(a[i][j])
for before in sorted(S):
if before != v:
adj[before].append(v) # v phải in trước before
ans = True
def dfs(u):
nonlocal ans
if not ans:
return
state[u] = 1
for v in adj[u]:
if state[v] == 1: # gặp lại đỉnh đang thăm: có chu trình
ans = False
return
if state[v] == 0:
dfs(v)
state[u] = 2
for u in range(1, 61):
if state[u] == 0:
dfs(u)
return ans
def main():
data = sys.stdin.read().split()
t = int(data[0])
p = 1
for _ in range(t):
n, m = int(data[p]), int(data[p + 1])
a = [[int(data[p + 2 + i * m + j]) for j in range(m)] for i in range(n)]
p += 2 + n * m
print("true" if Solution().isPrintable(a) else "false")
main()Em bấm Tiếp trong khung chạy tay dưới đây để xem từng dòng code C++ chạy. Code luôn duyệt đủ 60 màu, nên với những màu không có trong bảng mình gom phần quét bảng thành một bước cho đỡ dài (em có thể chọn tốc độ "Rất nhanh" hoặc bấm ⏭ rồi lùi lại). Khung "Dữ liệu" vẽ bảng $a$ (ô trong khung của màu đang xét tô tím, ô đang xét tô vàng), tập S, danh sách kề adj và state của các màu có trong bảng:
Đánh giá độ phức tạp của cách làm này:
- Không gian: bảng $N \cdot M$, đồ thị có tối đa 60 đỉnh và $60 \cdot 59$ cạnh ⇒ $O(N \cdot M)$.
- Thời gian: với mỗi màu trong 60 màu, ta quét cả bảng để tìm khung rồi quét khung ⇒ $O(60 \cdot N \cdot M)$, cỡ $60 \cdot 3600 \approx 2 \cdot 10^5$ phép toán; DFS trên đồ thị 60 đỉnh không đáng kể. Vì số màu bị chặn bởi hằng số 60 nên cũng có thể xem là $O(N \cdot M)$.
adj, state, ans là biến toàn cục, trên LeetCode một lần chạy sẽ gọi hàm isPrintable cho nhiều test liên tiếp. Nên đầu hàm bắt buộc phải clear và gán lại state[v] = 0, ans = true, nếu không test sau sẽ dính dữ liệu của test trước.Cách 2Cùng đồ thị, sắp xếp topo kiểu Kahn – O(60·N·M)
Thay vì DFS tìm chu trình, ta có thể mô phỏng luôn việc in: màu nào không phải chờ màu nào khác (bậc vào bằng 0) thì in trước, in xong thì "gỡ" các cạnh đi ra từ nó, màu nào hết phải chờ thì cho vào hàng đợi. Đây chính là thuật toán sắp xếp topo Kahn. Nếu in được hết các màu có trong bảng thì đồ thị không có chu trình ⇒ true; nếu có màu mãi không in được (kẹt trong chu trình) ⇒ false.
edge[v][k] để không thêm trùng cạnh (giúp đếm bậc vào chính xác). Khung chữ nhật của mọi màu được tính trong một lần quét bảng, nhưng phần duyệt các khung vẫn là $O(60 \cdot N \cdot M)$ trong trường hợp xấu nhất. Ưu điểm: không đệ quy, và hàng đợi cho ra luôn một thứ tự in cụ thể.Source code để các bạn tham khảo nếu làm theo hướng này:
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool isPrintable(vector<vector<int>>& a) {
int n = (int) a.size(), m = (int) a[0].size();
// khung chữ nhật nhỏ nhất bao các ô của từng màu
vector<int> x1(61, 65), y1(61, 65), x2(61, -1), y2(61, -1);
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++) {
int c = a[i][j];
x1[c] = min(x1[c], i); y1[c] = min(y1[c], j);
x2[c] = max(x2[c], i); y2[c] = max(y2[c], j);
}
// cạnh v -> k: màu v phải in trước màu k
vector<vector<bool>> edge(61, vector<bool>(61, false));
vector<int> indeg(61, 0);
for (int v = 1; v <= 60; v++) {
if (x2[v] == -1) continue;
for (int i = x1[v]; i <= x2[v]; i++)
for (int j = y1[v]; j <= y2[v]; j++) {
int k = a[i][j];
if (k != v && !edge[v][k]) {
edge[v][k] = true;
indeg[k]++;
}
}
}
// sắp xếp topo (Kahn): lần lượt lấy màu không còn phải chờ màu nào
queue<int> q;
int cnt = 0, total = 0;
for (int v = 1; v <= 60; v++) {
if (x2[v] == -1) continue;
total++;
if (indeg[v] == 0) q.push(v);
}
while (!q.empty()) {
int u = q.front(); q.pop();
cnt++;
for (int k = 1; k <= 60; k++)
if (edge[u][k] && --indeg[k] == 0) q.push(k);
}
return cnt == total; // in được hết các màu <=> không có chu trình
}
};
int main() {
int T;
cin >> T;
while (T--) {
int n, m;
cin >> n >> m;
vector<vector<int>> a(n, vector<int>(m));
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++) cin >> a[i][j];
Solution sol;
cout << (sol.isPrintable(a) ? "true" : "false") << "\n";
}
return 0;
}import sys
from collections import deque
from typing import List
class Solution:
def isPrintable(self, a: List[List[int]]) -> bool:
n, m = len(a), len(a[0])
# khung chữ nhật nhỏ nhất bao các ô của từng màu
x1, y1, x2, y2 = [65] * 61, [65] * 61, [-1] * 61, [-1] * 61
for i in range(n):
for j in range(m):
c = a[i][j]
x1[c] = min(x1[c], i); y1[c] = min(y1[c], j)
x2[c] = max(x2[c], i); y2[c] = max(y2[c], j)
# cạnh v -> k: màu v phải in trước màu k
edge = [set() for _ in range(61)]
indeg = [0] * 61
for v in range(1, 61):
if x2[v] == -1:
continue
for i in range(x1[v], x2[v] + 1):
for j in range(y1[v], y2[v] + 1):
k = a[i][j]
if k != v and k not in edge[v]:
edge[v].add(k)
indeg[k] += 1
# sắp xếp topo (Kahn)
colors = [v for v in range(1, 61) if x2[v] != -1]
q = deque(v for v in colors if indeg[v] == 0)
cnt = 0
while q:
u = q.popleft()
cnt += 1
for k in edge[u]:
indeg[k] -= 1
if indeg[k] == 0:
q.append(k)
return cnt == len(colors) # in được hết các màu <=> không có chu trình
def main():
data = sys.stdin.read().split()
t = int(data[0])
p = 1
for _ in range(t):
n, m = int(data[p]), int(data[p + 1])
a = [[int(data[p + 2 + i * m + j]) for j in range(m)] for i in range(n)]
p += 2 + n * m
print("true" if Solution().isPrintable(a) else "false")
main()true), so với code vét cạn "bóc ngược" từng lớp màu – khớp hết (363 test true, 137 test false). Với bảng $60 \times 60$ ngẫu nhiên và bảng 30 hình vuông lồng nhau, cả 4 code đều chạy dưới 0.1 giây.- Không biết học gì trước, học gì sau, học lan man nên kiến thức bị hổng.
- Bí bài không ai gỡ, ngồi cả buổi vẫn không ra rồi bỏ cuộc.
- Code chạy được nhưng không đủ điểm, không biết sai ở đâu, chậm ở đâu.
- Không có đề thi thử và người chấm, nên không biết mình đang ở mức nào.
- Dễ nản giữa chừng khi không có ai theo sát.
- Lộ trình 111 buổi video sắp sẵn từ dòng code đầu tiên đến đề HSG thật của các tỉnh.
- Thầy trực tiếp gỡ bí, chữa bài cho từng em qua nhóm Zalo riêng.
- Hệ thống chấm bài tự động 24/7 và thi thử HSG hằng tuần để biết chính xác mình đang ở đâu.
- Đóng học phí một lần, thầy kèm lâu dài: từ thi chuyên Tin đến HSG quốc gia và cả khi lên đại học.
Nhận xét
Đăng nhận xét