[暑假集训Day3T2]骑士问题
2024-09-04 20:25:39
标准的广搜。
采用队列保存形态,如果不会广搜的可以多看看PJ知识点。由于输入多组数据,每次标记数组要清空,每次队列元素也都要清空。
参考代码如下:
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
int t,n,x1,y1,x2,y2;
int dx[]={-,,,,,-,-,-},dy[]={,,,-,-,-,-,};
bool f[][];
struct node
{
int x,y,step;
};
int read()
{
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-;ch=getchar();}
return x*f;
}
void bfs()
{
node h;
h.x=x1;h.y=y1;h.step=;
queue<node>q;
q.push(h);
f[h.x][h.y]=;
while(!q.empty())
{
node k=q.front();
q.pop();
for(int i=;i<=;i++)
{
int xx=k.x+dx[i],yy=k.y+dy[i];
if(f[xx][yy]||xx<||yy<||xx>n||yy>n)continue;
node pus;
pus.x=xx;pus.y=yy;pus.step=k.step+;
f[xx][yy]=;
if(xx==x2&&yy==y2)
{
cout<<pus.step<<endl;
return;
}
q.push(pus);
}
}
}
int main()
{
//freopen("1.in","r",stdin);
t=read();
while(t--)
{
memset(f,,sizeof(f));
n=read();x1=read();y1=read();x2=read();y2=read();
if(x1==x2&&y1==y2)cout<<<<endl;
bfs();
}
return ;
}
最新文章
- window.self ->;window.top->;window.parent
- hdu 3336 kmp+next数组应用
- c# 重新认识 Double 浮点型
- web前端之 DOM
- Prisma
- 图画hadoop -- 生态圈
- 刨根究底字符编码之十三——UTF-16编码方式
- 【转】MYSQL 使用SQLyog导入遇到问题解决
- Python——Pycharm安装、激活、中文、
- 第一册:lesson ninety-nine。
- python之匿名函数以及在内置函数中的使用
- GALV_maptravel研究分析(1)
- <;Hadoop>;<;SequenceFile>;<;Hadoop小文件>;
- 20155331《网络对抗》 Exp9 Web安全基础
- CF933A A Twisty Movement
- Python中“if __name__==&#39;__main__&#39;:”理解与总结
- RESTful Web API 实践
- 【转】iOS-APP如何做才安全
- 利用反射及ActionFilterAttribute实现MVC权限管理
- MySQL 5.7 解压版 安装教程(图文详细)[Windows]
热门文章
- jsp页面随页面初始化加载js函数
- Java 遇到的困难
- Rsync+sersync 数据同步指南
- Sql在Group by的select中包含多列
- php $_SERVER 中的 QUERY_STRING和REQUEST_URI
- TFRecords文件的生成和读取(1)
- 一个能极大提高生产率的Chrome新建标签页扩展
- 对logistic回归分析的两重认识
- Primary Key Increase by Trigger
- 2018 ACM-ICPC 中国大学生程序设计竞赛线上赛 I. Reversion Count (java大数)