马的遍历

2025.9.14 曹立

题目内容

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

输入描述

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

输出描述

一个 \(n \times m\) 的矩阵，代表马到达某个点最少要走几步（不能到达则输出 \(-1\)）

输入输出样例

输入

3 3 1 1

输出

0 3 2
3 -1 1
2 1 4

C++实现

#include<iostream>
#include<queue>
using namespace std;
struct node{long long x,y;
};
long long n,m,x,y,vis[405][405],mark[405][405],cnt=0;
int dx[10]={2,2,1,1,-1,-1,-2,-2};
int dy[10]={1,-1,2,-2,2,-2,1,-1};
queue<node> q;
void putit()
{for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cout<<mark[i][j]<<" ";}cout<<endl;}
}
void bfs()
{for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)mark[i][j]=-1;q.push(node{x,y});mark[x][y]=0;while(!q.empty()){node temp=q.front();q.pop();for(int i=0;i<8;i++){long long xx=temp.x+dx[i],yy=temp.y+dy[i];if(xx>n || yy>m || xx<1 || yy<1 || mark[xx][yy]!=-1){continue;}q.push(node{xx,yy});mark[xx][yy]=mark[temp.x][temp.y]+1;}}
}
int main(void)
{cin>>n>>m>>x>>y;bfs();putit();return 0;}