Hướng dẫn giải của Phú yên_ bài 2
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 đếm số thành phần liên thông của các ký tự 'x' trong một lưới 2D. Hai ô được coi là liên thông nếu chúng kề nhau theo 4 hướng (trên, dưới, trái, phải). Input là một lưới các ký tự, trong đó 'x' đại diện cho các ô cần xét và các ký tự khác (như '0') là các ô trống/chướng ngại vật. Output là số lượng các cụm 'x' riêng biệt.
Các cách tiếp cận
Cách DFS (Duyệt theo chiều sâu) - Backtracking
#include <iostream>
#include <vector>
#define len size()
#define fi first
#define se second
using namespace std;
pair<int,int> moves[4] = {{1,0},{0,1},{-1,0},{0,-1}};
vector<string> ar;
int res = 0;
void backtrack(int i,int j){
ar[i][j] = '0'; // Đánh dấu đã thăm
for(auto mv:moves){
int ci = i + mv.fi;
int cj = j + mv.se;
if(0<=ci&&ci<ar.len&&0<=cj&&cj<ar[i].len&&ar[ci][cj]=='x') backtrack(ci,cj);
}
}
int main(){
ios::sync_with_stdio(0); cin.tie(); cout.tie();
freopen("bai2.inp","r",stdin);
freopen("bai2.out","w",stdout);
for(string x; cin>>x;) ar.push_back(x);
for(int i=0;i<ar.len;i++){
for(int j=0;j<ar[i].len;j++){
if(ar[i][j] == '0') continue;
res++;
backtrack(i,j);
}
}
cout<<res;
}
- Time Complexity: O(R * C)
- Space Complexity: O(R * C)
Phương pháp này duyệt qua từng ô trong lưới. Nếu gặp ô 'x' chưa được thăm, ta tăng biến đếm lên 1 và gọi đệ quy (DFS). Trong đệ quy, ta đánh dấu ô hiện tại là '0' (hoặc một ký tự khác) để tránh thăm lại, sau đó đệ quy sang các ô kề nhau nếu chúng là 'x'. Khi đệ quy kết thúc, một cụm 'x' đã được xử lý xong. Phương pháp này sử dụng stack của hệ điều hành cho đệ quy.
Cách BFS (Duyệt theo chiều rộng)
#include <bits/stdc++.h>
#define int long long
#define F first
#define S second
using namespace std;
const int N = 1e4;
int n = 0, m;
string a[N + 5];
bool vis[N + 5][N + 5];
int dx[] = {0, 0, 1, -1};
int dy[] = {-1, 1, 0, 0};
void bfs(int s1, int s2){
queue<pair<int, int>> q;
vis[s1][s2] = true;
q.push({s1, s2});
while(!q.empty()){
int u = q.front().F;
int v = q.front().S;
q.pop();
for(int i = 0; i < 4; ++i){
int x = u + dx[i];
int y = v + dy[i];
if(x >= 0 && x < n && y >= 0 && y < m && !vis[x][y] && a[x][y] == 'x'){
vis[x][y] = true;
q.push({x, y});
}
}
}
}
void Solve(){
while (getline(cin, a[n])) n++;
m = a[0].size();
int cnt = 0;
for(int i = 0; i < n; ++i){
for(int j = 0; j < m; ++j){
if(!vis[i][j] && a[i][j] == 'x'){
bfs(i, j);
cnt++;
}
}
}
cout << cnt;
}
signed main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
Solve();
}
- Time Complexity: O(R * C)
- Space Complexity: O(R * C)
Tương tự DFS, nhưng thay vì dùng đệ quy, ta dùng một hàng đợi (queue). Khi gặp một cụm 'x' mới, ta đẩy ô đó vào queue và xử lý lần lượt. BFS đảm bảo duyệt hết một cụm theo từng lớp nền. Phương pháp này thường an toàn hơn DFS đối với lưới rất lớn (tránh tràn stack), và logic xử lý rõ ràng hơn.
Cách Đồ thị (Sử dụng Map)
#include <bits/stdc++.h>
using namespace std;
#define task "bai2"
#define ll long long
#define vll vector<ll>
#define pll pair<ll, ll>
#define pli pair<ll, int>
#define pii pair<int, int>
#define ld long double
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define reggin ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
void inp() {
if (fopen(task".inp", "r")) {
freopen(task".inp", "r", stdin);
freopen(task".out", "w", stdout);
}
}
const int dx[] = {0, 0, -1, 1}, dy[] = {-1, 1, 0, 0};
vector<string> a;
int r, c;
map <pii, bool> vis;
void dfs(int x, int y) {
vis[{x, y}] = 1;
for (int d = 0; d < 4; d++) {
int nx = x + dx[d];
int ny = y + dy[d];
if (nx < 0 or nx >= r or ny < 0 or ny >= c or vis[{nx, ny}] or a[nx][ny] == '0') continue;
dfs(nx, ny);
}
}
signed main() {
inp();
reggin;
string s;
while (cin >> s) a.push_back(s);
r = a.size();
if(r > 0) c = a[0].size();
int cnt = 0;
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
if (a[i][j] == 'x' && !vis[{i, j}]) {
dfs(i, j);
cnt++;
}
}
}
cout << cnt;
}
- Time Complexity: O(N log N)
- Space Complexity: O(N)
Phương pháp này sử dụng map để lưu trạng thái đã thăm (thay vì mảng 2D). Đây là cách tiếp cận linh hoạt khi tọa độ có thể rất lớn hoặc thưa (sparse). Tuy nhiên, trong bài toán lưới thông thường với kích thước vừa phải, nó chậm hơn do chi phí truy cập và lưu trữ map (O(log N)).
Phân tích độ phức tạp
| Cách tiếp cận | Time | Space | Tên |
|---|---|---|---|
| 1 | O(R * C) | O(R * C) | DFS (Duyệt theo chiều sâu) - Backtracking |
| 2 | O(R * C) | O(R * C) | BFS (Duyệt theo chiều rộng) |
| 3 | O(N log N) | O(N) | Đồ thị (Sử dụng Map) |
Bài học kinh nghiệm
- Bài toán là bài toán đếm số thành phần liên thông (Connected Components) kề nhau theo 4 hướng.
- Cần phân biệt rõ ràng giữa việc đánh dấu đã thăm (visited) và việc thay đổi giá trị ô hiện tại ('x' thành '0' trong Solution 3). Cả hai đều hợp lệ nhưng Solution 1 & 2 (sử dụng mảng visited hoặc map) an toàn hơn nếu cần giữ nguyên dữ liệu lưới.
- DFS/BFS là những thuật toán chuẩn để duyệt các thành phần liên thông.
Lỗi thường gặp
- Quên kiểm tra biên (boundary checks) khi truy cập các ô lân cận, dẫn đến lỗi truy cập ngoài bộ nhớ.
- Lỗi đọc input: Sử dụng
cin >> ssẽ bỏ qua khoảng trắng và xuống dòng. Nếu lưới chứa các ký tự khoảng trắng, cần dùnggetline. Solution 1 sử dụnggetlinelà một cách an toàn. - Tràn stack (Stack Overflow) với DFS đệ quy nếu lưới quá lớn hoặc cụm 'x' quá dài. BFS thường là lựa chọn an toàn hơn trong các tình huống này.
Bình luận