Hướng dẫn giải của Miền 0
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
Bài toán yêu cầu tìm kích thước của vùng 0 lớn nhất trong một lưới M x N. Input là hai số nguyên M, N và một ma trận M hàng, N cột chứa các giá trị 0 và 1. Vùng 0 được định nghĩa là một tập hợp các ô chứa giá trị 0 mà các ô này kề nhau theo 4 hướng (lên, xuống, trái, phải). Output là số lượng ô trong vùng 0 lớn nhất tìm được.
Các cách tiếp cận
Cách DFS (Duyệt theo chiều sâu)
#include <bits/stdc++.h>
using namespace std;
int m, n;
int a[105][105], v[105][105];
int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,1,-1};
int dfs(int x, int y)
{
v[x][y] = 1;
int c = 1;
for (int k = 0; k < 4; k++)
{
int u = x + dx[k], w = y + dy[k];
if (u >= 0 && u < m && w >= 0 && w < n && !v[u][w] && a[u][w] == 0)
c += dfs(u,w);
}
return c;
}
int main()
{
freopen("bai3.inp", "r", stdin);
freopen("bai3.out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> m >> n;
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
cin >> a[i][j];
int r = 0;
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
if (a[i][j] == 0 && !v[i][j])
r = max(r, dfs(i,j));
cout << r;
}
- Time Complexity: O(M * N)
- Space Complexity: O(M * N)
Approach này sử dụng thuật toán DFS (Duyệt theo chiều sâu) kết hợp với đệ quy. Khi gặp một ô chưa được duyệt và có giá trị 0, ta gọi đệ quy từ ô đó. Hàm dfs sẽ đánh dấu ô hiện tại là đã duyệt, đếm chính nó (c = 1), và sau đó kiểm tra 4 ô lân cận. Nếu ô lân cận hợp lệ (nằm trong lưới, chưa duyệt, và là ô 0), ta gọi đệ quy cho ô đó và cộng dồn kết quả vào biến đếm. Kết quả cuối cùng là giá trị lớn nhất trong tất cả các lần gọi dfs.
Cách BFS (Duyệt theo chiều rộng)
#include <bits/stdc++.h>
using namespace std;
int M, N;
int a[105][105];
bool vis[105][105];
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
freopen("bai3.inp", "r", stdin);
freopen("bai3.out", "w", stdout);
cin >> M >> N;
for (int i = 0; i < M; i++)
for (int j = 0; j < N; j++)
cin >> a[i][j];
int best = 0;
for (int i = 0; i < M; i++) {
for (int j = 0; j < N; j++) {
if (!vis[i][j] && a[i][j] == 0) {
int area = 0;
queue<pair<int,int>> q;
q.push({i, j});
vis[i][j] = true;
while (!q.empty()) {
auto [x, y] = q.front(); q.pop();
area++;
for (int k = 0; k < 4; k++) {
int nx = x + dx[k], ny = y + dy[k];
if (nx >= 0 && nx < M && ny >= 0 && ny < N && !vis[nx][ny] && a[nx][ny] == 0) {
q.push({nx, ny});
vis[nx][ny] = true;
}
}
}
best = max(best, area);
}
}
}
cout << best;
}
- Time Complexity: O(M * N)
- Space Complexity: O(M * N)
Approach này sử dụng thuật toán BFS (Duyệt theo chiều rộng) kết hợp với hàng đợi (queue). Khi gặp ô chưa được duyệt và là ô 0, ta tạo một hàng đợi, đưa ô đó vào và đánh dấu đã duyệt. Trong khi hàng đợi chưa rỗng, ta lấy một ô ra, tăng biến đếm diện tích, và kiểm tra 4 ô lân cận. Nếu ô lân cận hợp lệ, ta đưa vào hàng đợi và đánh dấu đã duyệt. Cách này khác DFS ở chỗ nó duyệt theo từng lớp khoảng cách từ ô nguồn.
Cách DFS/BFS với xử lý mảng truy vấn trực tiếp (In-place)
#include <bits/stdc++.h>
#define ll long long
#define DOWNTIME ios_base::sync_with_stdio(false);cin.tie(NULL); cout.tie(NULL);
#define FIXED(x) fixed << setprecision(x)
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FORD(i, a, b) for (int i = (a); i >= (b); i--)
#define fi first
#define se second
#define pb push_back
using namespace std;
const int mx = 1e3 + 1;
int n, m;
int a[mx][mx];
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
int vs[mx][mx];
bool check(int x, int y) {
return (x >= 1 && x <= n && y >= 1 && y <= m);
}
int loang(int x, int y) {
queue <pair <int, int>> q;
int ans = 0;
memset(vs, 0, sizeof(vs));
q.push({x, y});
vs[x][y] = 1;
ans++;
while (!q.empty()) {
pair <int, int> p = q.front(); q.pop();
FOR(i, 0, 3) {
int nx = p.fi + dx[i];
int ny = p.se + dy[i];
if (check(nx, ny) && a[nx][ny] == 0 && !vs[nx][ny]) {
vs[nx][ny] = 1;
ans++;
q.push({nx, ny});
}
}
}
return ans;
}
int main() {
DOWNTIME
freopen("bai3.inp", "r", stdin);
freopen("bai3.out", "w", stdout);
cin >> n >> m;
int res = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> a[i][j];
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (a[i][j] == 0 && !vs[i][j]) {
res = max(res, loang(i, j));
}
}
}
cout << res;
return 0;
}
- Time Complexity: O(M * N)
- Space Complexity: O(M * N)
Đây là biến thể của BFS, chỉ khác biệt về cú pháp và cách khai báo biến. Code sử dụng #define để rút gọn mã nguồn và dùng chỉ số mảng bắt đầu từ 1. Logic cốt lõi vẫn là duyệt qua từng ô, khi gặp ô 0 chưa duyệt thì dùng BFS (hàng đợi) để đếm kích thước vùng 0 kề nhau. Cách tiếp cận này cho thấy sự linh hoạt trong lập trình nhưng bản chất thuật toán tương tự như BFS.
Phân tích độ phức tạp
| Cách tiếp cận | Time | Space | Tên |
|---|---|---|---|
| 1 | O(M * N) | O(M * N) | DFS (Duyệt theo chiều sâu) |
| 2 | O(M * N) | O(M * N) | BFS (Duyệt theo chiều rộng) |
| 3 | O(M * N) | O(M * N) | DFS/BFS với xử lý mảng truy vấn trực tiếp (In-place) |
Bài học kinh nghiệm
- Bài toán có thể giải quyết hiệu quả bằng các thuật toán duyệt đồ thị cơ bản (DFS hoặc BFS) trên lưới.
- Một vùng 0 liên thông chính là một thành phần liên thông (Connected Component) trong đồ thị mà các đỉnh là ô 0 và các cạnh là sự kề nhau.
- Độ phức tạp thời gian O(M*N) là tối ưu vì chúng ta cần duyệt qua tất cả các phần tử của lưới ít nhất một lần.
Lỗi thường gặp
- Quên kiểm tra điều kiện biên (boundary check) khi truy cập các ô lân cận (ví dụ: hàng xóm nằm ngoài lưới), dẫn đến lỗi truy cập bộ nhớ ngoài.
- Quên đánh dấu ô đã duyệt (visited) trước khi đưa vào hàng đợi (trong BFS) hoặc trước khi gọi đệ quy (trong DFS), dẫn đến việc một ô được tính nhiều lần hoặc gây ra vòng lặp vô hạn (stack overflow với DFS đệ quy).
- Sử dụng mảng visited全局 hoặc mảng a全局 nhưng không reset hoặc khai báo đúng kích thước (đặc biệt trong các bài thi nhiều test case).
Bình luận