P1443 马的遍历
# P1443 马的遍历
## 题目描述
有一个 $n \times m$ 的棋盘，在某个点 $(x, y)$ 上有一个马，要求你计算出马到达棋盘上任意一个点最少要走几步。
## 输入格式
输入只有一行四个整数，分别为 $n, m, x, y$。
## 输出格式
一个 $n \times m$ 的矩阵，代表马到达某个点最少要走几步（不能到达则输出 $-1$）。
## 输入输出样例 #1
### 输入 #1
```
3 3 1 1
```
### 输出 #1
```
0 3 2
3 -1 1
2 1 4
```
## 说明/提示
### 数据规模与约定
对于全部的测试点，保证 $1 \leq x \leq n \leq 400$，$1 \leq y \leq m \leq 400$。
题目描述 有一个n*m的棋盘(1<n,m<=400)，在某个点上有一个马,要求你计算出马到达棋盘上任意一个点最少要走几步 输入格式 一行四个数据，棋盘的大小和马的坐标 输出格式 一个n乘m的矩阵，代表马到达某个点最少要走几步（左对齐，宽5格，不能到达则输出-1） 输入输出样例 输入 3 3 1 1 输出 0 3 2
3 -1 1
2 1 4
分析 这道题我们可以用深搜（BFS） 很简单，不会BFS的可以参考 骑士旅行（BFS） AC代码
#include<iostream>
#include<cstdio>
int n,m,x1,y1,head,tail,a[405][405],b[405][405],st[160005][3];
int dx[9]={0,1,1,-1,-1,2,2,-2,-2};//八个方向
int dy[9]={0,2,-2,2,-2,1,-1,1,-1};
void bfs()
{while(head<tail)//BFS模板{head++;for(int i=1;i<=8;i++)//八个方向{int x=st[head][0]+dx[i],y=st[head][1]+dy[i];if(x>=1&&x<=n&&y>=1&&y<=m)//是否出界if(a[x][y]==0)//是否被标记过{tail++;a[x][y]=1;//标记b[x][y]=st[tail][2]=st[head][2]+1;//赋值st[tail][0]=x;//更新坐标st[tail][1]=y;}}}
}
using namespace std;
int main()
{cin>>n>>m;cin>>x1>>y1;a[x1][y1]=1;//标记st[1][0]=x1;st[1][1]=y1;//坐标tail=1;//初值bfs();for(int i=1;i<=n;i++){for(int j=1;j<=m;j++)if(a[i][j]!=0)printf("%-5d",b[i][j]);//输出需要else printf("%-5d",-1);cout<<endl;}
}
