本文共 1815 字，大约阅读时间需要 6 分钟。
题目描述：
给出初始结束位置，问8步以内能否走到？
题解：
从初始结束位置一起跑4步。
也称meet_in_the_middle
代码：
#include#include #include #include #include #include using namespace std;bool ck(int x,int y){ return x>=1&&x<=8&&y>=1&&y<=8;}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 mp1,mp2; queue q1,q2,tmp; int hs1,hs2,x,y,tx,ty; hs1 = a.v(),hs2=b.v(); if(hs1==hs2)return 1; mp1[hs1]=mp2[hs2]=1; q1.push(a),q2.push(b); for(register int dep=1;dep<=4;dep++) { while(!q1.empty()) { u = q1.front(); q1.pop(); for(register int i=1;i<=4;i++) { x = u.s[i].x,y = u.s[i].y; for(register int j=0;j<4;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=1;i<=4;i++) { x = u.s[i].x,y = u.s[i].y; for(register int j=0;j<4;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 0;}int main(){ while(scanf("%d%d",&a.s[1].x,&a.s[1].y)>0) { for(int i=2;i<=4;i++)scanf("%d%d",&a.s[i].x,&a.s[i].y); for(int i=1;i<=4;i++)scanf("%d%d",&b.s[i].x,&b.s[i].y); sort(a.s+1,a.s+5,cmp),sort(b.s+1,b.s+5,cmp); printf(bfs()?"YES\n":"NO\n"); } return 0;}
转载于:https://www.cnblogs.com/LiGuanlin1124/p/10002645.html