P1443 马的遍历
2022/8/24 23:26:36
本文主要是介绍P1443 马的遍历,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
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;
}
这篇关于P1443 马的遍历的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?
- 2024-05-09这种运行结果里的10.100000001,怎么能最快改成10.1?
- 2024-05-09企业src漏洞挖掘-有意思的命令执行
- 2024-05-08阿里云域名注册流程,分享给第一次购买域名的新手站长!