题目描述:
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 ;
}

最新文章

  1. const和readonly区别
  2. Jquery dialog属性
  3. lua中常量的实现及表的深拷贝实现
  4. 如何将 Microsoft Bot Framework 链接至微信公共号
  5. IMP 导入数据报错 OCI-21500 OCI-22275
  6. 近 100 个 Linux 常用命令大全
  7. 编程算法 - 最小的k个数 红黑树 代码(C++)
  8. loading.io一个loading图标网站,跟大家分享
  9. ASP.NET前台table通过Ajax获取绑定后台查询的json数据
  10. Android开发:文本控件详解——TextView(一)基本属性
  11. python 中 try catch finally语句中含有return语句的执行情况
  12. Js浮点运算存在精度问题
  13. Python3实现自动点赞抖音小姐姐
  14. 【CentOS 7】CentOS7与CentOS6 的区别
  15. 《Linux课本》读书笔记 第十七章 模块
  16. 2019.02.09 codeforces451 E. Devu and Flowers(容斥原理)
  17. 8.3Solr API使用(StatsComponent聚合统计)
  18. python引入pytesseract报错:ValueError: Attempted relative import in non-package
  19. php 四种基础排序
  20. ORTP&amp;&amp;RTSP

热门文章

  1. Python科学计算工具包
  2. 虚拟机安装hadoop
  3. 【黑金教程笔记之002】【建模篇】【Lab 01 永远的流水灯】—笔记&amp;勘误
  4. 洛谷 P2762 太空飞行计划问题 【最大权闭合子图+最小割】
  5. 11.3NOIP模拟赛
  6. NOIp 2010/Luogu P1525 关押罪犯 【二分图/并查集】 By cellur925
  7. 2017 JUST Programming Contest 3.0 D. Dice Game
  8. 积分图像 分类: 图像处理 Matlab 2015-06-06 10:30 149人阅读 评论(0) 收藏
  9. js插件之Ocupload
  10. vue组件中—bus总线事件回调函数多次执行的问题