Hướng dẫn giải của [CSES 3217] Knight Moves Grid
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.
Đầu tiên ta đặt số ~0~ vào ô góc trên bên trái. Sau đó, với ~x=1,2,3,\dots~, ta đặt số ~x~ vào tất cả các ô chưa thăm mà có thể đến được trong một nước đi từ một ô chứa số ~x-1~. Quá trình này tiếp tục cho đến khi tất cả các ô đều được thăm.
Cách tiếp cận này có thể được cài đặt hiệu quả bằng cách sử dụng một hàng đợi lưu các ô theo thứ tự khoảng cách tăng dần. Thuật toán tương tự như thuật toán tìm kiếm theo chiều rộng (BFS).
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n;
cin >> n;
vector<vector<int>> grid(n, vector<int>(n, -1));
vector<pair<int, int>> queue;
grid[0][0] = 0;
queue.emplace_back(0, 0);
int dy[8] = {1, 1, -1, -1, 2, 2, -2, -2};
int dx[8] = {2, -2, 2, -2, 1, -1, 1, -1};
for (int i = 0; i < queue.size(); i++) {
auto [y, x] = queue[i];
for (int d = 0; d < 8; d++) {
int ny = y + dy[d];
int nx = x + dx[d];
if (ny < 0 || ny >= n || nx < 0 || nx >= n || grid[ny][nx] != -1) {
continue;
}
grid[ny][nx] = grid[y][x] + 1;
queue.emplace_back(ny, nx);
}
}
for (int y = 0; y < n; y++) {
for (int x = 0; x < n; x++) {
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;
cin >> n;
vector<vector<int>> grid(n, vector<int>(n, -1));
vector<pair<int, int>> queue;
grid[0][0] = 0;
queue.emplace_back(0, 0);
int dy[8] = {1, 1, -1, -1, 2, 2, -2, -2};
int dx[8] = {2, -2, 2, -2, 1, -1, 1, -1};
for (int i = 0; i < queue.size(); i++) {
auto [y, x] = queue[i];
for (int d = 0; d < 8; d++) {
int ny = y + dy[d];
int nx = x + dx[d];
if (ny < 0 || ny >= n || nx < 0 || nx >= n || grid[ny][nx] != -1) {
continue;
}
grid[ny][nx] = grid[y][x] + 1;
queue.emplace_back(ny, nx);
}
}
for (int y = 0; y < n; y++) {
for (int x = 0; x < n; x++) {
cout << grid[y][x] << " ";
}
cout << "\n";
}
}
Bình luận