当前位置:网站首页>1330:【例8.3】最少步数
1330:【例8.3】最少步数
2022-07-05 14:47:00 【暴揍键盘的程序猿】
1330:【例8.3】最少步数
时间限制: 1000 ms 内存限制: 65536 KB
提交数: 13863 通过数: 7606
【题目描述】
在各种棋中,棋子的走法总是一定的,如中国象棋中马走“日”。有一位小学生就想如果马能有两种走法将增加其趣味性,因此,他规定马既能按“日”走,也能如象一样走“田”字。他的同桌平时喜欢下围棋,知道这件事后觉得很有趣,就想试一试,在一个(100×100)的围棋盘上任选两点A、B,A点放上黑子,B点放上白子,代表两匹马。棋子可以按“日”字走,也可以按“田”字走,俩人一个走黑马,一个走白马。谁用最少的步数走到左上角坐标为(1,1)的点时,谁获胜。现在他请你帮忙,给你A、B两点的坐标,想知道两个位置到(1,1)点可能的最少步数。
【输入】
A、B两点的坐标。
【输出】
最少步数。
【输入样例】
12 16
18 10
【输出样例】
8
9
【算法分析】
由于A、B两点是随机输入的,因此无法找到计算最少步数的数学规律,只能通过广度优先搜索的办法求解。
(1)确定出发点
从(n,m)出发通过一次广度优先搜索,可以找到从(n,m)至棋盘上所有可达点的最少步数。而问题中要求的是黑马所在的(x1,yy1)和白马所在(x2,y2)到达(1,1)目标点的最少步数。虽然两条路径的起点不一样,但是它们的终点却是一样的。如果我们将终点(1,1)作为起点,这样只需要一次广度优先搜索便可以得到(x1,yy1)和(x2,y2)到达(1,1)的最少步数。
(2)数据结构
设queue——队列,存储从(1,1)可达的点(queue[k][1..2])以及到达该点所需要的最少步数(queue[k][3])(0k192+1)。队列的首指针为head,尾指针为tail。初始时,queue中只有一个元素为(1,1),最少步数为0。
a——记录(1,1)到每点所需要的最少步数。显然,问题的答案是a[x1][yy1]和a[x2][y2]。初始时,a[1][1]为0,除此之外的所有元素值设为-1。
dx、dy——移动后的位置增量数组。马有12种不同的扩展方向:
马走“日”:
(n-2,m-1)(n-1,m-2)(n-2,m+1)(n-1,m+2)(n+2,m-1)(n+1,m-2)(n+2,m+1)(n+1,m+2)
马走“田”:
(n-2,m-2)(n-2,m+2)(n+2,m-2)(n+2,m+2)
我们将i方向上的位置增量存入常量数组dx[i]、dy[i]中(0i11):
int dx[12]={-1,-1,-1,1,2,2,2,2,1,-1,-2,-2},dy[12]={-1,-2,-2,-2,-2,-1,1,2,2,2,2,1};
(3)约束条件
(1)不能越出界外。由于马的所有可能的落脚点a均在a的范围内,因此一旦马越出界外,就将其a值赋为0,表示“已经扩展过,且(1,1)到达其最少需要0步”。这看上去是荒谬的,但可以简单而有效地避免马再次落入这些界外点。
(2)该点在以前的扩展中没有到达过。如果曾经到达过,则根据广度优先搜索的原理,先前到达该点所需的步数一定小于当前步数,因此完全没有必要再扩展下去。
由此得出,马的跳后位置(n,m)是否可以入队的约束条件是a[n][m]0。
(4)算法流程
【AC代码】
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iomanip>
#include<iostream>
#include<map>
#include<queue>
#include<string>
#include<vector>
using namespace std;
const int N=1e3+10;
inline int fread()
{
char ch=getchar();
int n=0,m=1;
while(ch<'0' or ch>'9')
{
if(ch=='-')m=-1;
ch=getchar();
}
while(ch>='0' and ch<='9')n=(n<<3)+(n<<1)+ch-48,ch=getchar();
return n*m;
}
int dx[12]={-1,-1,-1,1,2,2,2,2,1,-1,-2,-2},dy[12]={-1,-2,-2,-2,-2,-1,1,2,2,2,2,1},a[N][N],q[10000][4],x1,yy1,x2,y2,head=1,tail=1;//初始位置入队
signed main()
{
memset(a,0xff,sizeof a),q[1][1]=q[1][2]=1,q[1][3]=0,x1=fread(),yy1=fread(),x2=fread(),y2=fread();//a数组的初始化,读入黑马和白马的出发位置
while(head<=tail)
{
for(int i=0;i<12;i++)//枚举12个扩展方向
{
int n=q[head][1]+dx[i],m=q[head][2]+dy[i];//计算马按i方向跳跃后的位置
if(n>0 and m>0)
if(a[n][m]==-1)//若(n,m)满足约束条件
{
a[n][m]=q[head][3]+1,tail++,q[tail][1]=n,q[tail][2]=m,q[tail][3]=a[n][m];//计算(1,1)到(n,m)的最少步数,(1,1)至(n,m)的最少步数入队
if(a[x1][yy1]>0 and a[x2][y2]>0)//输出问题的解
{
cout<<a[x1][yy1]<<"\n";
cout<<a[x2][y2]<<"\n";
return 0;
}
}
}
head++;
}
return 0;
}
我喜欢用数组模拟队列
(还不是因为不想记队列的操作函数)。
边栏推荐
- [detailed explanation of Huawei machine test] happy weekend
- 注意!软件供应链安全挑战持续升级
- 浅谈Dataset和Dataloader在加载数据时如何调用到__getitem__()函数
- SaaS multi tenant solution for FMCG industry to build digital marketing competitiveness of the whole industry chain
- CODING DevSecOps 助力金融企业跑出数字加速度
- Type declaration of all DOM elements in TS
- Disjoint Set
- Is it OK to open the securities account on the excavation finance? Is it safe?
- 机器学习笔记 - 灰狼优化
- webRTC SDP mslabel lable
猜你喜欢
【NVMe2.0b 14-9】NVMe SR-IOV
用 Go 跑的更快:使用 Golang 为机器学习服务
Countermeasures of enterprise supply chain management system in UCA Era
计算中间件 Apache Linkis参数解读
12 MySQL interview questions that you must chew through to enter Alibaba
freesurfer运行完recon-all怎么快速查看有没有报错?——核心命令tail重定向
Chow Tai Fook fulfills the "centenary commitment" and sincerely serves to promote green environmental protection
Topology visual drawing engine
PyTorch二分类时BCELoss,CrossEntropyLoss,Sigmoid等的选择和使用
有一个强大又好看的,赛过Typora,阿里开发的语雀编辑器
随机推荐
freesurfer运行完recon-all怎么快速查看有没有报错?——核心命令tail重定向
可视化任务编排&拖拉拽 | Scaleph 基于 Apache SeaTunnel的数据集成
面试突击62:group by 有哪些注意事项?
CPU design practice - Chapter 4 practical task 2 using blocking technology to solve conflicts caused by related problems
How to choose the appropriate certificate brand when applying for code signing certificate?
mysql8.0JSON_CONTAINS的使用说明
Differences between IPv6 and IPv4 three departments including the office of network information technology promote IPv6 scale deployment
PostgreSQL 13 installation
World Environment Day | Chow Tai Fook serves wholeheartedly to promote carbon reduction and environmental protection
Penetration testing methodology
Talking about how dataset and dataloader call when loading data__ getitem__ () function
有一个强大又好看的,赛过Typora,阿里开发的语雀编辑器
Topology visual drawing engine
Reconnaissance des caractères easycr
Topology可视化绘图引擎
Install and configure Jenkins
实现一个博客系统----使用模板引擎技术
[summary of leetcode weekly competition] the 81st fortnight competition of leetcode (6.25)
【NVMe2.0b 14-9】NVMe SR-IOV
计算中间件 Apache Linkis参数解读