【「POJ1915」Knight Moves】题解

原题目链接：Link

gm : bfs的版题

没学过 bfs 的同学可以看代码注释，先理解意思。

#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;
const int Maxn = 300 + 5;
const int a[8] = {
    -2, -1, 1, 2, 2, 1, -1, -2}; // 增量数组
const int b[8] = {
    1, 2, 2, 1, -1, -2, -2, -1};
int n, l, sx, sy, ex, ey;
bool vis[Maxn][Maxn]; 
struct node {
    int x, y, step;
};
int bfs() {
    queue<node> q; // 定义队列q.push((node){
    sx, sy, 0}); // 存入起点信息while(!q.empty()) {
     // 非空node p = q.front();q.pop(); if(p.x == ex and p.y == ey) return p.step; // 是否到达终点for(int i = 0;i < 8; ++i) {
    int dx = p.x + a[i], dy = p.y + b[i]; // 在当前坐标的基础上能直接到达的新坐标if(dx >= 0 and dy >= 0 and dx < l and dy < l and !vis[dx][dy]) {
     // 判断是否可以到达vis[dx][dy] = 1; // 已经搜索q.push((node){
    dx, dy, p.step + 1}); // 存入新的信息}}} 
}
int main() {
    scanf("%d", &n);while(n --) {
    memset(vis, 0, sizeof(vis));scanf("%d %d %d %d %d", &l, &sx, &sy, &ex, &ey); // 不要被题目介绍熏昏了头脑printf("%d\n", bfs());}return 0;
}