Hướng dẫn giải của Hồ nước
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
, , ,
Editorial for lake: Hồ nước
Hiểu bài toán
Bài toán yêu cầu tìm kích thước lớn nhất của một hồ nước trên một cánh đồng dạng lưới. Cánh đồng có kích thước M x N. Một số ô bị ngập nước (được cho trước). Một hồ nước là một tập hợp các ô ngập nước liên thông với nhau (theo 4 hướng: lên, xuống, trái, phải). Ta cần tìm ra hồ nước có số lượng ô lớn nhất.
Các cách tiếp cận
Cách DFS (Duyệt theo độ sâu)
#include <bits/stdc++.h>
using namespace std;
int m, n, k;
int a[105][105];
bool visited[105][105];
int max_size = 0;
int current_size = 0;
int dx[4] = {-1, 0, 0, 1};
int dy[4] = {0, -1, 1, 0};
void dfs(int i, int j) {
visited[i][j] = true;
current_size++;
for (int k = 0; k < 4; k++) {
int i1 = i + dx[k];
int j1 = j + dy[k];
if (i1 >= 1 && i1 <= m && j1 >= 1 && j1 <= n && !visited[i1][j1] && a[i1][j1] == 1) {
dfs(i1, j1);
}
}
}
int main() {
cin >> m >> n >> k;
memset(a, 0, sizeof(a));
memset(visited, false, sizeof(visited));
for (int i = 0; i < k; i++) {
int x, y;
cin >> x >> y;
a[x][y] = 1;
}
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (a[i][j] == 1 && !visited[i][j]) {
current_size = 0;
dfs(i, j);
max_size = max(max_size, current_size);
}
}
}
cout << max_size << endl;
return 0;
}
- Time Complexity: O(M * N)
- Space Complexity: O(M * N)
Đây là cách tiếp cận trực quan nhất. Ta duyệt qua từng ô của lưới. Nếu gặp một ô ngập nước chưa được thăm, ta bắt đầu một cuộc duyệt DFS từ ô đó. DFS sẽ thăm đệ quy tất cả các ô ngập nước liền kề chưa được thăm và đếm chúng. Kích thước của mỗi thành phần liên thông (lake) được ghi nhận để tìm ra kích thước lớn nhất. Do ta chỉ duyệt qua mỗi ô một lần, độ phức tạp thời gian là O(M*N).
Cách BFS (Duyệt theo chiều rộng)
#include <bits/stdc++.h>
using namespace std;
int m, n, k;
int a[105][105];
bool visited[105][105];
int dx[4] = {-1, 0, 0, 1};
int dy[4] = {0, -1, 1, 0};
int bfs(int start_x, int start_y) {
int cnt = 0;
queue<pair<int, int>> q;
q.push({start_x, start_y});
visited[start_x][start_y] = true;
while (!q.empty()) {
pair<int, int> u = q.front();
q.pop();
cnt++;
for (int k = 0; k < 4; k++) {
int i1 = u.first + dx[k];
int j1 = u.second + dy[k];
if (i1 >= 1 && i1 <= m && j1 >= 1 && j1 <= n && !visited[i1][j1] && a[i1][j1] == 1) {
visited[i1][j1] = true;
q.push({i1, j1});
}
}
}
return cnt;
}
int main() {
cin >> m >> n >> k;
for (int i = 0; i < k; i++) {
int x, y;
cin >> x >> y;
a[x][y] = 1;
}
int max_size = 0;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (a[i][j] == 1 && !visited[i][j]) {
max_size = max(max_size, bfs(i, j));
}
}
}
cout << max_size << endl;
return 0;
}
- Time Complexity: O(M * N)
- Space Complexity: O(M * N)
Cách tiếp cận này tương tự DFS nhưng sử dụng Queue để duyệt. Khi gặp một ô ngập nước chưa được thăm, ta thêm nó vào hàng đợi. Lấy các ô ra khỏi hàng đợi, ta đếm và thêm các láng giềng ngập nước chưa thăm vào hàng đợi. BFS đảm bảo duyệt hết một thành phần liên thông trước khi chuyển sang thành phần khác. Kết quả tương đương DFS nhưng thường an toàn hơn về mặt stack memory (tránh stack overflow) với các lưới lớn.
Cách DFS Thay Đổi (In-place)
#include <bits/stdc++.h>
using namespace std;
int m, n, k;
int a[1011][1011]; // Mảng lớn hơn một chút cho an toàn
int ans = 0;
int len = 0;
int dx[4] = {-1, 0, 0, 1};
int dy[4] = {0, -1, 1, 0};
void lake(int i, int j) {
len++;
a[i][j] = 0; // Đánh dấu đã thăm bằng cách sửa đổi trực tiếp giá trị
for (int k = 0; k < 4; k++) {
int i1 = i + dx[k];
int j1 = j + dy[k];
if (i1 > 0 && i1 <= m && j1 > 0 && j1 <= n && a[i1][j1] == 1) {
lake(i1, j1);
}
}
}
int main() {
cin >> m >> n >> k;
for (int i = 1; i <= k; i++) {
int x, y;
cin >> x >> y;
a[x][y] = 1;
}
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (a[i][j] == 1) {
len = 0;
lake(i, j);
ans = max(ans, len);
}
}
}
cout << ans;
return 0;
}
- Time Complexity: O(M * N)
- Space Complexity: O(M * N)
Đây là biến thể của DFS. Thay vì dùng một mảng visited riêng, ta thay đổi giá trị của ô ngập nước thành 0 (hoặc một giá trị khác) sau khi thăm. Điều này giúp tiết kiệm bộ nhớ một chút và mã nguồn gọn hơn. Tuy nhiên, nếu yêu cầu bài toán không cho phép thay đổi dữ liệu đầu vào thì cách này không phù hợp. Logic duyệt vẫn là đệ quy theo 4 hướng.
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 độ 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 Thay Đổi (In-place) |
Bài học kinh nghiệm
- Bài toán có thể được xử lý bằng cách xem các ô ngập nước là các node và các đường đi giữa các ô kề nhau là các cạnh trong đồ thị. Tìm hồ lớn nhất tương đương với tìm thành phần liên thông lớn nhất trong đồ thị.
- DFS và BFS là 2 thuật toán chuẩn để duyệt các thành phần liên thông trong đồ thị 2 chiều.
- Sử dụng mảng đánh dấu (visited array) là bắt buộc để tránh duyệt lại các ô đã thuộc một hồ khác hoặc gây vòng lặp vô hạn.
Lỗi thường gặp
- Quên kiểm tra ranh giới của mảng (giá trị i, j có nằm trong [1, M] và [1, N] hay không) khi truy cập mảng, dẫn đến lỗi truy cập bộ nhớ ngoài.
- Sử dụng đệ quy DFS quá sâu (với M, N lên tới 100, độ sâu tối đa là 10,000) có thể gây tràn bộ nhớ đệm (stack overflow) trong một số môi trường lập trình thi đấu, do đó BFS hoặc đệ quy tưưởng (nếu hỗ trợ) là lựa chọn an toàn hơn.
- Đọc sai input: Đề bài cho K dòng, mỗi dòng tọa độ (x, y). Cần đảm bảo khởi tạo ma trận và đọc đúng số lượng.
Bình luận