复习总结提高版
#include <iostream>
#define f(inc, frm, to) for (size_t inc = frm; inc < to; ++inc)
using namespace std;
const int N = 310;
typedef struct Coordinate {
int x, y;
} Coord;
int t, n, sx, sy, tx, ty;
inline int BFS(void) {
Coord q[N * N];
int seen[N][N] = {0}, front = 0, rear = 0;
q[rear++] = {sx, sy};
seen[sy][sx] = 1;
constexpr int dirs[][2] {-1,-2,-2,-1,-2,1,-1,2,1,2,2,1,2,-1,1,-2};
int steps = 0;
while (front < rear) {
size_t s = rear - front;
while (s--) {
const int x = q[front].x, y = q[front].y; ++front;
// printf("%d %d\n", y, x);
if (x == tx and y == ty) return steps;
f(d, 0, 8) {
int nx = x + dirs[d][0], ny = y + dirs[d][1];
if (not(nx >= 0 and nx < n and ny >= 0 and ny < n and not seen[ny][nx]))
continue;
q[rear++] = {nx, ny};
seen[ny][nx] = 1;
}
}
++steps;
}
return -1;
}
int main() {
cin >> t;
while (t--) {
cin >> n >> sy >> sx >> ty >> tx;
// printf("%d %d %d %d %d\n", n, sy, sx, ty, tx);
cout << BFS() << endl;
}
return 0;
}
BFS Template 时间复杂度$O(N^2)$ 每个格子最多访问一次
#include <iostream>
#include <queue>
using namespace std;
using P = pair<int, int>;
static constexpr int dirs[][2] {{2, -1}, {1, -2}, {-1, -2}, {-2, -1},
{-2, 1}, {-1, 2}, {1, 2}, {2, 1}};
int t;
int bfs(vector<vector<int>>& grid, const int n, int sx, int sy, int tx, int ty) {
queue<P> q;
q.emplace(sx, sy);
grid[sx][sy] = 1; // mark as visited
int steps = 0;
while (not q.empty()) {
int sz = q.size();
while (sz--) {
const auto [x, y] = q.front(); q.pop();
if (x == tx && y == ty) return steps;
for (int i = 0; i < 8; ++i) {
const int nx = x + dirs[i][0], ny = y + dirs[i][1];
if (nx < 0 || ny < 0 || nx >= n || ny >= n || grid[nx][ny]) continue;
grid[nx][ny] = 1; // mark as visited
q.emplace(nx, ny);
}
}
++steps;
}
return steps;
}
int main() {
cin >> t;
while (t--) {
int n, sx, sy, tx, ty;
cin >> n >> sx >> sy >> tx >> ty;
vector<vector<int>> grid(n, vector<int>(n, 0));
cout << bfs(grid, n, sx, sy, tx, ty) << endl;
}
return 0;
}