HDU1401 Solitaire
2024-09-06 02:31:04
题目描述:
8×8的棋盘上有4个棋子,棋子的运动方法如下:
1.如果其上/下/左/右一格没有棋子,则可以去;2.如果其上/下/左/右一格有棋子,而且沿原方向再跳一步没有,则可以去。
给出初始结束位置,问8步以内能否走到?
题解:
双向BFS。
从初始结束位置一起跑4步。
也称meet_in_the_middle
代码:
#include<map>
#include<queue>
#include<vector>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
bool ck(int x,int y){return x>=&&x<=&&y>=&&y<=;}
struct P
{
int x,y;
P(){}
P(int x,int y):x(x),y(y){}
};
bool cmp(P a,P b)
{
if(a.x==b.x)return a.y<b.y;
return a.x<b.x;
}
struct sp
{
P s[];
int v()
{
int hs = ;
for(int i=;i<=;i++)hs=hs*+(s[i].x-)*+s[i].y-;
return hs;
}
bool emp(int x,int y)
{
if(!ck(x,y))return ;
for(int i=;i<=;i++)if(s[i].x==x&&s[i].y==y)return ;
return ;
}
void bal()
{
sort(s+,s+,cmp);
}
}a,b,u,t;
int dx[]={-,,,},dy[]={,,-,};
int bfs()
{
map<int,int>mp1,mp2;
queue<sp>q1,q2,tmp;
int hs1,hs2,x,y,tx,ty;
hs1 = a.v(),hs2=b.v();
if(hs1==hs2)return ;
mp1[hs1]=mp2[hs2]=;
q1.push(a),q2.push(b);
for(register int dep=;dep<=;dep++)
{
while(!q1.empty())
{
u = q1.front();
q1.pop();
for(register int i=;i<=;i++)
{
x = u.s[i].x,y = u.s[i].y;
for(register int j=;j<;j++)
{
t=u;
tx=x+dx[j],ty=y+dy[j];
if(!t.emp(tx,ty))
{
tx+=dx[j],ty+=dy[j];
}
if(t.emp(tx,ty))
{
t.s[i].x=tx,t.s[i].y=ty;
t.bal();
hs1 = t.v();
if(mp2[hs1])return dep+mp2[hs1];
if(!mp1[hs1])
{
mp1[hs1]=dep;
tmp.push(t);
}
}
}
}
}
while(!tmp.empty())q1.push(tmp.front()),tmp.pop();
while(!q2.empty())
{
u = q2.front();
q2.pop();
for(register int i=;i<=;i++)
{
x = u.s[i].x,y = u.s[i].y;
for(register int j=;j<;j++)
{
t=u;
tx=x+dx[j],ty=y+dy[j];
if(!t.emp(tx,ty))
{
tx+=dx[j],ty+=dy[j];
}
if(t.emp(tx,ty))
{
t.s[i].x=tx,t.s[i].y=ty;
t.bal();
hs2 = t.v();
if(mp1[hs2])return dep+mp1[hs2];
if(!mp2[hs2])
{
mp2[hs2]=dep;
tmp.push(t);
}
}
}
}
}
while(!tmp.empty())q2.push(tmp.front()),tmp.pop();
}
return ;
}
int main()
{
while(scanf("%d%d",&a.s[].x,&a.s[].y)>)
{
for(int i=;i<=;i++)scanf("%d%d",&a.s[i].x,&a.s[i].y);
for(int i=;i<=;i++)scanf("%d%d",&b.s[i].x,&b.s[i].y);
sort(a.s+,a.s+,cmp),sort(b.s+,b.s+,cmp);
printf(bfs()?"YES\n":"NO\n");
}
return ;
}
最新文章
- const和readonly区别
- Jquery dialog属性
- lua中常量的实现及表的深拷贝实现
- 如何将 Microsoft Bot Framework 链接至微信公共号
- IMP 导入数据报错 OCI-21500 OCI-22275
- 近 100 个 Linux 常用命令大全
- 编程算法 - 最小的k个数 红黑树 代码(C++)
- loading.io一个loading图标网站,跟大家分享
- ASP.NET前台table通过Ajax获取绑定后台查询的json数据
- Android开发:文本控件详解——TextView(一)基本属性
- python 中 try catch finally语句中含有return语句的执行情况
- Js浮点运算存在精度问题
- Python3实现自动点赞抖音小姐姐
- 【CentOS 7】CentOS7与CentOS6 的区别
- 《Linux课本》读书笔记 第十七章 模块
- 2019.02.09 codeforces451 E. Devu and Flowers(容斥原理)
- 8.3Solr API使用(StatsComponent聚合统计)
- python引入pytesseract报错:ValueError: Attempted relative import in non-package
- php 四种基础排序
- ORTP&;&;RTSP
热门文章
- Python科学计算工具包
- 虚拟机安装hadoop
- 【黑金教程笔记之002】【建模篇】【Lab 01 永远的流水灯】—笔记&;勘误
- 洛谷 P2762 太空飞行计划问题 【最大权闭合子图+最小割】
- 11.3NOIP模拟赛
- NOIp 2010/Luogu P1525 关押罪犯 【二分图/并查集】 By cellur925
- 2017 JUST Programming Contest 3.0 D. Dice Game
- 积分图像 分类: 图像处理 Matlab 2015-06-06 10:30 149人阅读 评论(0) 收藏
- js插件之Ocupload
- vue组件中—bus总线事件回调函数多次执行的问题