Hướng dẫn giải của [CSES 1624] Chessboard and Queens
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.
Đoạn mã sau cài đặt một thuật toán quay lui để đếm số nghiệm. Hàm search thêm một quân hậu vào hàng ~y~ và sau đó thêm quân hậu tiếp theo một cách đệ quy. Khi tất cả các quân hậu đã được đặt lên bàn cờ, một nghiệm mới đã được tìm thấy.
Để đảm bảo không có hai quân hậu nào tấn công nhau, mã sử dụng ba mảng:
coltheo dõi các cột có quân hậudiag1theo dõi các đường chéo (hướng thứ nhất) có quân hậudiag2theo dõi các đường chéo (hướng thứ hai) có quân hậu
#include <iostream>
using namespace std;
const int N = 8;
string grid[N];
int total;
bool col[N], diag1[2 * N], diag2[2 * N];
void search(int y) {
if (y == N) {
total++;
return;
}
for (int x = 0; x < N; x++) {
if (grid[y][x] == '*') {
continue;
}
if (col[x] || diag1[x + y] || diag2[y - x + N]) {
continue;
}
col[x] = diag1[x + y] = diag2[y - x + N] = true;
search(y + 1);
col[x] = diag1[x + y] = diag2[y - x + N] = false;
}
}
int main() {
for (auto &row : grid) {
cin >> row;
}
search(0);
cout << total << "\n";
}
Tài liệu tham khảo
Chương trình tham khảo
#include <iostream>
using namespace std;
const int N = 8;
string grid[N];
int total;
bool col[N], diag1[2 * N], diag2[2 * N];
void search(int y) {
if (y == N) {
total++;
return;
}
for (int x = 0; x < N; x++) {
if (grid[y][x] == '*') {
continue;
}
if (col[x] || diag1[x + y] || diag2[y - x + N]) {
continue;
}
col[x] = diag1[x + y] = diag2[y - x + N] = true;
search(y + 1);
col[x] = diag1[x + y] = diag2[y - x + N] = false;
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
for (auto &row : grid) {
cin >> row;
}
search(0);
cout << total << "\n";
}
Bình luận