Hướng dẫn giải của [CSES 3311] Grid Coloring I
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
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.
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.
Ta có thể giải bài toán một cách tham lam bằng cách duyệt qua lưới từ trên xuống dưới và từ trái sang phải.
Với mỗi ô, ta chọn ký tự đầu tiên không phải là ký tự ban đầu của ô đó và cũng không trùng với ký tự bên trái hoặc ký tự phía trên. Vì có bốn ký tự khả dĩ, ta luôn có thể tìm được một ký tự hợp lệ.
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector<string> grid(n);
for (int i = 0; i < n; i++) {
cin >> grid[i];
}
for (int y = 0; y < n; y++) {
for (int x = 0; x < m; x++) {
for (int c = 'A'; c <= 'D'; c++) {
bool fail = false;
if (grid[y][x] == c) fail = true;
if (y > 0 && grid[y - 1][x] == c) fail = true;
if (x > 0 && grid[y][x - 1] == c) fail = true;
if (!fail) {
grid[y][x] = c;
break;
}
}
cout << grid[y][x];
}
cout << "\n";
}
}
Chương trình tham khảo
#include <iostream>
#include <vector>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<string> grid(n);
for (int i = 0; i < n; i++) {
cin >> grid[i];
}
for (int y = 0; y < n; y++) {
for (int x = 0; x < m; x++) {
for (int c = 'A'; c <= 'D'; c++) {
bool fail = false;
if (grid[y][x] == c) fail = true;
if (y > 0 && grid[y - 1][x] == c) fail = true;
if (x > 0 && grid[y][x - 1] == c) fail = true;
if (!fail) {
grid[y][x] = c;
break;
}
}
cout << grid[y][x];
}
cout << "\n";
}
}
Bình luận