Hướng dẫn giải của Tô màu tranh
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ố lượng vùng màu đồng nhất trong một lưới N x M. Mỗi ô trong lưới có một giá trị nguyên biểu diễn màu sắc. Hai ô được coi là cùng một vùng nếu chúng có cùng màu và kề nhau theo chiều ngang hoặc chiều dọc (tức là chung một cạnh). Mục tiêu là tìm tổng số vùng màu khác nhau trong lưới.
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 dx[4] = {-1, 0, 0, 1};
int dy[4] = {0, -1, 1, 0};
int a[2501][2501];
int n, m;
int kq = 0;
void search(int i, int j) {
int goal = a[i][j];
a[i][j] = -1; // Đánh dấu đã thăm bằng cách thay đổi giá trị
for (int k = 0; k < 4; k++) {
int i1 = i + dx[k];
int j1 = j + dy[k];
if (i1 >= 1 && j1 >= 1 && i1 <= n && j1 <= m && a[i1][j1] == goal) {
search(i1, j1);
}
}
}
int main() {
freopen("PICTURE.INP", "r", stdin);
freopen("PICTURE.OUT", "w", stdout);
cin >> n >> m;
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] != -1) {
search(i, j);
kq++;
}
}
}
cout << kq;
return 0;
}
- Time Complexity: O(N * M)
- Space Complexity: O(N * M)
Đây là cách tiếp cận trực quan nhất. Chúng ta duyệt qua từng ô của lưới. Nếu gặp một ô chưa được duyệt (giá trị khác -1), ta thực hiện thuật toán DFS từ ô đó. Trong hàm DFS, ta đánh dấu ô hiện tại là đã duyệt và đệ quy sang các ô kề cạnh cùng màu. Mỗi lần gọi DFS thành công (tức là gặp ô chưa duyệt) tương ứng với việc tìm thấy một vùng màu mới, do đó ta tăng biến đếm lên 1. DFS sẽ duyệt và đánh dấu toàn bộ các ô thuộc cùng một vùng.
Cách BFS (Duyệt theo chiều rộng)
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int MAX = 2500;
int M, N;
int color[MAX][MAX];
bool visited[MAX][MAX];
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
void bfs(int x, int y) {
queue<pair<int, int>> q;
q.push({x, y});
visited[x][y] = true;
int currentColor = color[x][y];
while (!q.empty()) {
auto [cx, cy] = q.front(); q.pop();
for (int dir = 0; dir < 4; ++dir) {
int nx = cx + dx[dir];
int ny = cy + dy[dir];
if (nx >= 0 && nx < M && ny >= 0 && ny < N &&
!visited[nx][ny] && color[nx][ny] == currentColor) {
visited[nx][ny] = true;
q.push({nx, ny});
}
}
}
}
int main() {
freopen("picture.inp", "r", stdin);
freopen("picture.out", "w", stdout);
cin >> M >> N;
for (int i = 0; i < M; ++i) {
for (int j = 0; j < N; ++j) {
cin >> color[i][j];
}
}
int regions = 0;
for (int i = 0; i < M; ++i) {
for (int j = 0; j < N; ++j) {
if (!visited[i][j]) {
bfs(i, j);
regions++;
}
}
}
cout << regions << endl;
return 0;
}
- Time Complexity: O(N * M)
- Space Complexity: O(N * M)
Cách tiếp cận này tương tự DFS nhưng sử dụng thuật toán BFS. Thay vì đệ quy, ta sử dụng một hàng đợi (queue) để lưu các ô cần duyệt. Khi gặp một ô chưa duyệt, ta thêm nó vào hàng đợi và liên tục lấy các ô ra để duyệt các ô kề cạnh chưa duyệt. BFS thường an toàn hơn với stack overflow so với DFS đệ quy khi xử lý lưới lớn, nhưng về độ phức tạp thời gian và bộ nhớ là tương đương.
Cách DFS với Mảng Đánh Dấu (Thay đổi trực tiếp)
#include <bits/stdc++.h>
#define int long long
#define endl "\n"
#define TranHungss(); ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
const int maxn = 2555;
int n, m, a[maxn][maxn];
int dx[4] = {1, 0, 0, -1};
int dy[4] = {0, -1, 1, 0};
void DFS(int i, int j, int pos){
a[i][j] = -1;
for(int k = 0; k < 4; k++){
int i1 = i + dx[k];
int j1 = j + dy[k];
if(i1 >= 1 && i1 <= n && j1 >= 1 && j1 <= m && a[i1][j1] == pos){
DFS(i1, j1, pos);
}
}
}
signed main(){
TranHungss();
ifstream cin("PICTURE.INP");
ofstream cout("PICTURE.OUT");
cin >> n >> m;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
cin >> a[i][j];
}
}
int res = 0;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
if(a[i][j] != -1){
++res;
DFS(i, j, a[i][j]);
}
}
}
cout << res;
return 0;
}
- Time Complexity: O(N * M)
- Space Complexity: O(N * M)
Đây là biến thể của DFS. Điểm khác biệt là hàm DFS nhận thêm tham số pos (giá trị màu sắc ban đầu) để so sánh với các ô kề cạnh, thay vì phụ thuộc vào giá trị của ô hiện tại (vì ô hiện tại đã bị thay đổi thành -1). Việc này đảm bảo tính chính xác khi duyệt đệ quy. Đây là cách tối ưu về mặt bộ nhớ so với việc dùng mảng visited riêng.
Phân tích độ phức tạp
| Cách tiếp cận | Time | Space | Tên |
|---|---|---|---|
| 1 | O(N * M) | O(N * M) | DFS (Duyệt theo chiều sâu) |
| 2 | O(N * M) | O(N * M) | BFS (Duyệt theo chiều rộng) |
| 3 | O(N * M) | O(N * M) | DFS với Mảng Đánh Dấu (Thay đổi trực tiếp) |
Bài học kinh nghiệm
- Bài toán có thể được giải quyết bằng cách mô hình hóa lưới dưới dạng đồ thị, trong đó mỗi ô là một node và các cạnh nối giữa các ô kề nhau. Bài toán trở thành bài toán đếm số thành phần liên thông (Connected Components).
- Các thuật toán DFS hoặc BFS là công cụ phù hợp để duyệt và đánh dấu các thành phần liên thông này.
- Việc sử dụng chính ma trận input để đánh dấu (ví dụ: thay đổi giá trị đã duyệt thành -1) giúp tiết kiệm bộ nhớ so với việc sử dụng một mảng visited riêng.
Lỗi thường gặp
- Lỗi chỉ số mảng: Cần chú ý độ dài mảng (ví dụ 2501 hoặc 2555) và cách truy cập (0-based hoặc 1-based) sao cho phù hợp với quy mô đề bài và cách nhập xuất.
- Tràn sốc (Stack Overflow): Nếu dùng DFS đệ quy trên lưới lớn (2500x2500), độ sâu đệ quy có thể lên tới 6.25 triệu, dễ gây tràn sốc. Trong trường hợp này, BFS hoặc DFSiterative (dùng stack) là an toàn hơn.
- Lỗi logic khi sửa đổi trực tiếp: Khi sửa đổi trực tiếp giá trị trong mảng a, cần đảm bảo logic kiểm tra điều kiện kề cạnh đúng. Ví dụ, nếu dùng
a[i][j]làm giá trị mục tiêu sau khi đã gána[i][j] = -1thì sẽ sai. Cần lưu giá trị ban đầu trước khi duyệt.
Bình luận