这题也就两个难点， 第一：我们要怎么走，从一个状态走到另一个状态，每个点有四个方向共四个点，那就16种情况不难啊，跨一步的意思就是沿原来的方向再走一步即可 第二：状态怎么存，我本来想要用map<stu,int> 结果运行实在太慢了，后面看看题解，看上了人家的8维数组，结果因为我是双向BFS,写两个超内存了。。。后面想想，其实可以把它看出一个十进制数，八位十进制不就可了吗，但为了再省点，我用了24位的二进制储存，差不多，如何映射，不就一map!!! 就这样子AC了 双向和单向感觉没啥差别就是在主函数多写了个dfs，就没了。 上代码
#include <iostream> #include <cstdio> #include <algorithm> #include <vector> #include <queue> #include <map> #include <cstring> using namespace std; int dir[4][2] = {{0,1},{1,0},{-1,0},{0,-1}};//四个转移 map<int , int > V,V1; //对应是否有那个状态 struct k{ int x,y; bool operator < ( const k& b) const{ if ( x == b.x ) return y < b.y; return x < b.x; }//排序用的 }; struct stu{ k a[4]; int vis;//记录第几步 }s[2]; int BFS(stu s,int kk){ queue <stu> q; stu be,nex; sort(s.a,s.a+4); int Z = 0; for (int i = 0; i < 4; i++) { Z+= s.a[i].x << (6*i); Z+= s.a[i].y << (6*i+3); }//对应每个状态 总共八个点把其从大到小排序后即可化为一个24位的二进制来表示 if(!kk){ V[Z] = 1; } else{ V1[Z] = 1; if(V[Z]) return 1;//二次进入的时候直接判断一下有木有走过即可 } be = s; q.push(be); while(!q.empty()) { be = q.front(); q.pop(); if( be.vis == 4 ) break; for (int i = 0; i < 4; i++)//哪个 { int x = be.a[i].x,y = be.a[i].y; for (int j = 0; j < 4; j++)//位移 { int newx = x+dir[j][0],newy = y+dir[j][1]; for (int z = 0; z < 4; z++) { if(z != i && newx == be.a[z].x && newy == be.a[z].y) { newx += dir[j][0]; newy += dir[j][1]; } }//再继续翻 if (newx >= 1 && newy <= 8 && newy >= 1 && newy <= 8) { nex = be; nex.a[i].x = newx; nex.a[i].y = newy; sort(nex.a,nex.a+4); nex.vis = be.vis + 1; int Z = 0; for (int i = 0; i < 4; i++) // 转为24位二进制 { Z+= nex.a[i].x << (6*i); Z+= nex.a[i].y << (6*i+3); } if(!kk) { if(! V.count(Z)){ V[Z] = 1; q.push(nex); } } else { if(! V1.count(Z)){ V1[Z] = 1; if(V[Z]) return 1; q.push(nex); } }//同理 } } } } return 0; } int main() { while(~scanf("%d%d",&s[0].a[0].x,&s[0].a[0].y)) { for (int i = 0; i < 2; i++) { for (int j = 0; j < 4; j++) { if(!i && !j) continue; scanf("%d%d",&s[i].a[j].x,&s[i].a[j].y); } } V.clear(); V1.clear(); s[0].vis = 0; s[1].vis = 0;//初始化 BFS(s[0],0); if(BFS(s[1],1)) printf("YES\n"); else printf("NO\n"); } return 0; }