Hướng dẫn giải của Đếm hình vuông
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Lời giải này đang bị ẩn cho đến khi bạn chọn mở ra.
Chúng tôi khuyên bạn nên tự thử giải bài trước. Việc mở lời giải có thể làm lộ mất ý tưởng chính trước khi bạn có cơ hội tự giải.
Bạn phải đăng nhập để mở lời giải này.
Đăng nhập
Tác giả: Hiếu Nguyễn
, , ,
Hiểu bài toán
Cho một bảng kích thước M x N gồm các giá trị 0 và 1. Nhiệm vụ là đếm tổng số các hình vuông con (liền mạch, không bị ngắt quãng) mà tất cả các ô trong đó đều chứa giá trị 0. Các hình vuông có thể có kích thước khác nhau (1x1, 2x2, ..., kxk) và có thể nằm ở bất kỳ vị trí nào trong bảng sao cho nó vẫn nằm trong phạm vi.
Các cách tiếp cận
Cách Brute Force (Duyệt tất cả các hình vuông)
#include <bits/stdc++.h>
using namespace std;
int main() {
int m, n;
cin >> m >> n;
vector<string> a(m);
for (int i = 0; i < m; i++) cin >> a[i];
long long ans = 0;
// Duyệt đỉnh trên bên trái (i, j) của hình vuông
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
// Duyệt kích thước k của hình vuông
for (int k = 0; i + k < m && j + k < n; k++) {
bool ok = true;
// Kiểm tra hàng mới nhất được thêm vào
for (int col = j; col <= j + k; col++) {
if (a[i + k][col] == '1') {
ok = false;
break;
}
}
if (!ok) break;
// Kiểm tra cột mới nhất được thêm vào (tránh kiểm tra trùng ô góc)
for (int row = i; row <= i + k - 1; row++) {
if (a[row][j + k] == '1') {
ok = false;
break;
}
}
if (!ok) break;
ans++;
}
}
}
cout << ans;
}
- Time Complexity: O(M * N * min(M, N)^2)
- Space Complexity: O(1) excluding input storage
Phương pháp này thử tất cả các vị trí bắt đầu (i, j) và tất cả các kích thước k có thể. Với mỗi hình vuông, nó kiểm tra thủ công xem tất cả các ô có phải là '0' không. Cách tiếp cận này dễ hiểu nhưng rất chậm do số lượng hình vuông cần kiểm tra rất lớn (khoảng O(M * N * min(M, N)^2) thao tác).
Cách Duyệt tất cả các hình vuông với Summed Area Table (Prefix Sum)
#include <bits/stdc++.h>
using namespace std;
int main() {
int m, n;
cin >> m >> n;
vector<vector<int>> a(m + 1, vector<int>(n + 1, 0));
// Đọc dữ liệu và xây dựng bảng tổng tiền tố
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
char x;
cin >> x;
a[i][j] = x - '0';
}
}
vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + a[i][j];
}
}
long long res = 0;
// Duyệt đỉnh trên bên trái (i, j)
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
// Duyệt kích thước k
for (int k = 0; i + k <= m && j + k <= n; k++) {
int end_row = i + k;
int end_col = j + k;
// Tính tổng số '1' trong vùng hình vuông
int sum = dp[end_row][end_col] - dp[i - 1][end_col] - dp[end_row][j - 1] + dp[i - 1][j - 1];
if (sum == 0) {
res++;
}
}
}
}
cout << res;
}
- Time Complexity: O(M * N * min(M, N))
- Space Complexity: O(M * N)
Phương pháp này sử dụng Bảng tổng tiền tố (Summed Area Table hoặc Prefix Sum 2D) để tính tổng các giá trị '1' trong một vùng chữ nhật bất kỳ trong thời gian O(1). Thay vì kiểm tra từng ô, ta chỉ cần kiểm tra xem tổng của vùng hình vuông có bằng 0 hay không. Vẫn cần duyệt qua tất cả các vị trí và kích thước, nhưng việc kiểm tra đã nhanh hơn rất nhiều so với duyệt lồng nhau.
Cách Quy hoạch động (Dynamic Programming)
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int m, n;
cin >> m >> n;
vector<string> a(m);
for (auto &x : a) cin >> x;
// dp[i][j] lưu độ dài cạnh lớn nhất của hình vuông toàn '0'
// có đỉnh dưới bên phải tại (i, j)
vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
long long ans = 0;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (a[i - 1][j - 1] == '0') {
// Công thức quy hoạch động
// dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
dp[i][j] = 1 + min({dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]});
// Số hình vuông kết thúc tại (i, j) chính là dp[i][j]
// Ví dụ: dp[i][j] = 3意味着 có 3 hình vuông (1x1, 2x2, 3x3) kết thúc ở đây
ans += dp[i][j];
}
}
}
cout << ans;
}
- Time Complexity: O(M * N)
- Space Complexity: O(M * N)
Đây là phương pháp tối ưu nhất. Ta định nghĩa dp[i][j] là độ dài cạnh lớn nhất của hình vuông toàn '0' có đỉnh dưới bên phải tại (i, j). Nếu ô (i, j) là '0', độ dài cạnh lớn nhất tại đây bằng 1 cộng với độ dài cạnh lớn nhất tại 3 ô kề bên (trên, trái, và chéo góc). Lý do là hình vuông con tại (i, j) chỉ có thể mở rộng ra nếu các hình vuông tại 3 vị trí kia cũng đủ lớn. Quan trọng hơn, nếu dp[i][j] = k, nghĩa là tại vị trí này có k hình vuông (kích thước từ 1 đến k) kết thúc. Do đó, ta chỉ cần cộng dồn dp[i][j] vào kết quả cuối cùng.
Phân tích độ phức tạp
| Cách tiếp cận | Time | Space | Tên |
|---|---|---|---|
| 1 | O(M * N * min(M, N)^2) | O(1) excluding input storage | Brute Force (Duyệt tất cả các hình vuông) |
| 2 | O(M * N * min(M, N)) | O(M * N) | Duyệt tất cả các hình vuông với Summed Area Table (Prefix Sum) |
| 3 | O(M * N) | O(M * N) | Quy hoạch động (Dynamic Programming) |
Bài học kinh nghiệm
- Vấn đề có thể được chia nhỏ thành bài toán đếm các hình vuông kết thúc tại một ô cụ thể nào đó.
- Nếu tại một ô (i, j) có một hình vuông toàn '0' có kích thước kxk, thì tại đó chắc chắn có k hình vuông (1x1, 2x2, ..., kxk).
Lỗi thường gặp
- Sử dụng kiểu dữ liệu
intcho biến kết quả nếu số lượng hình vuông lớn (ví dụ: bảng 1000x1000 toàn '0' sẽ có khoảng 3.33e8 hình vuông, vượt quá giới hạn 2 tỷ củaint). Nên dùnglong long. - Đánh chỉ số mảng sai trong các phép tính quy hoạch động (ví dụ: quên điều chỉnh chỉ số 1-based hoặc 0-based của input).
Bình luận