洛谷刷题C++语言 | P1443 马的遍历

学习C++从娃娃抓起！记录下洛谷C++学习和备考过程中的题目，记录每一个瞬间。

附上汇总贴：洛谷刷题C++语言 | 汇总_热爱编程的通信人的博客-CSDN博客

【题目描述】

有一个 n×m 的棋盘，在某个点 (x,y) 上有一个马，要求你计算出马到达棋盘上任意一个点最少要走几步。

【输入】

输入只有一行四个整数，分别为 n,m,x,y。

【输出】

一个 n×m 的矩阵，代表马到达某个点最少要走几步（不能到达则输出 ?1）。

【输入样例】

3 3 1 1

【输出样例】

0    3    2    
3    -1   1    
2    1    4    

【代码详解】

#include <bits/stdc++.h>
using namespace std;
int n, m, x, y, a[405][405];
struct node {
    int x, y;
};
int main()
{
    cin >> n >> m >> x >> y;
    int dx[8]={-1,-2,-2,-1,1,2,2,1}, dy[8]={-2,-1,1,2,2,1,-1,-2};
    memset(a, -1, sizeof(a));
    queue<node> q;
    node tp = {x, y};
    a[x][y]=0;
    q.push(tp);
    while (!q.empty()) {
        tp = q.front();
        q.pop();
        for (int i=0; i<8; i++) {
            int xx = tp.x+dx[i], yy = tp.y+dy[i];
            if (xx<1 || xx>n || yy<1 || yy>m || a[xx][yy]!=-1) continue;
            a[xx][yy] = a[tp.x][tp.y]+1;
            node t = {xx,yy};
            q.push(t);
        }
    }
    for (int i=1; i<=n; i++) {
        for (int j=1; j<=m; j++) {
            cout << a[i][j] << "    ";
        }
        cout << endl;
    }
    return 0;
}

【运行结果】

3 3 1 1
0    3    2
3    -1    1
2    1    4