马跳的步数c++实现输入的的第1行是一个整数n,表示以后会有n行数据。 从第2行开始,每行有4个整数,前2个数表示起点坐标,后2个数表示终点坐标。 输出格式: 对每行起点和终点坐标输出一个整数,表示从起点到终点最

短的马跳步数。以下是C++实现：

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

const int N = 405;
const int INF = 0x3f3f3f;

struct Edge {
    int to, nxt;
} edges[N * N];
int head[N], cnt;
int dis[N][N];
bool vis[N][N];
int dx[8] = {-2, -1, 1, 2, 2, 1, -1, -2};
int dy[8] = {1, 2, 2, 1, -1, -2, -2, -1};

void addEdge(int from, int to) {
    edges[++cnt].to = to;
    edges[cnt].nxt = head[from];
    head[from] = cnt;
}

void bfs(int x, int y) {
    memset(vis, false, sizeof(vis));
    queue<pair<int, int>> q;
    dis[x][y] = 0;
    vis[x][y] = true;
    q.push({x, y});
    while (!q.empty()) {
        auto [cx, cy] = q.front();
        q.pop();
        for (int i = 0; i < 8; i++) {
            int nx = cx + dx[i], ny = cy + dy[i];
            if (nx >= 1 && nx <= 400 && ny >= 1 && ny <= 400 && !vis[nx][ny]) {
                dis[nx][ny] = dis[cx][cy] + 1;
                vis[nx][ny] = true;
                q.push({nx, ny});
            }
        }
    }
}

int main() {
    int n;
    cin >> n;
    while (n--) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        if (dis[x1][y1] == INF) bfs(x1, y1);
        cout << dis[x2][y2] << endl;
    }
    return 0;
}

首先定义了一个结构体`Edge`来存储边的信息，以及一个邻接表`head`和一个计数器`cnt`来存储图的信息。`addEdge`函数用于添加边。`dx`和`dy`数组分别存储马在棋盘上的8个可行的方向。`bfs`函数用于求解从起点到棋盘上每个点的最短距离。在主程序中，首先读入数据，然后对于每个询问，如果起点的最短距离还没有被求解过，就调用`bfs`函数求解，然后输出终点的最短距离。