P1443 马的遍历
- 分析：根据题意，本题用bfs求解，马每次有八个方位的走向，将步数初始化为-1，这样如果没有马跳到这个地方就直接输出-1，使用队列先进先出的特点，在马每跳到一个方位后放到队尾，等待下一次跳马，其中要开结构体将矩阵图横纵坐标联系起来，每次在指定范围内跳完后更新点的位置并将步数+1。
-
#include<iostream>
#include<iomanip>
#include<queue>
#include<cstring>
using namespace std;
int a[401][401];//记录步数
int n,m,sx,sy;
int dx[8]={-2,-2,-1,1,2,2,1,-1};
int dy[8]={-1,1,2,2,1,-1,-2,-2};
struct node
{
int x,y;
}k,kk;//k每次在更新完新的值后进入队尾等待下一次跳马
void bfs(int x,int y)
{
a[x][y]=0;//初始步数为0
k.x=sx;//初始化 开始的点
k.y=sy;
queue<node> q;//队列
q.push(k);//从一开始的点进行跳马
while(!q.empty())
{
kk=q.front();//现下要跳马的点
q.pop();
for(int i=0;i<8;i++)//模拟八个方向
{
int xx=kk.x+dx[i];//每跳马看到哪
int yy=kk.y+dy[i];
if(a[xx][yy]==-1&&xx>=1&&xx<=n&&yy>=1&&yy<=m)
{//跳到的这个地方没被走过
k.x=xx;//可以跳 更新x y值到现在的位置
k.y=yy;
a[k.x][k.y]=a[kk.x][kk.y]+1;//记录步数
q.push(k);//刚跳完的点放入队尾准备下一次跳马
}
}
}
}
int main()
{
cin>>n>>m>>sx>>sy;
memset(a,-1,sizeof(a));
bfs(sx,sy);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
cout<<left<<setw(5)<<a[i][j];
cout<<endl;
}
return 0;
}