题目链接
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1505
题意 一个8 * 8 的棋盘上面有四个棋子
棋子可以上下左右移动，如果隔壁有个棋子 那就可以跳一步，只能跳一步。
给出 初始状态，和末尾状态 求能不能在8步之内达到
思路乍一眼看，这题就是一个搜索，但是虽然只有8步，但是每步都有4个点可以选择，每个点又有4个方向，所以复杂度为：（4*4）^8，可谓爆炸，那么就容易想到双向bfs,可以减小到2*（4*4）^4,起点和终点同时bfs,若在步数之内相交，说明是可行的。这里又有个难点：如何判断相交？首先对于这个8*8的图进行压缩，成一个100000000的数来表示状态，然后因为这个数太大，不能用数组来表示，所以我们用map来保存这个状态值，map的dis,来表示该搜索方式是否已经被搜索到，并且保存搜索到的步数长度#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <map>
#include <vector>
using namespace std;
#define N 8 // 图的大小int g[N][N];
int godir[][2] = {
{-1,0}, {0,1}, {1,0}, {0,-1}};int gtoi (int a[][N]) {int rs = 0;int loc = 10000000;for (int i = 0; i < N; ++i) {for (int j = 0; j < N; ++j) {if (a[i][j]==1) {rs += i*loc;loc /= 10;rs += j*loc;loc /= 10;}if(loc==1) break;}if(loc==1) break;}return rs;
}void itog(int a[][N], int st) {for(int i = 0; i < N; ++i) memset(a[i], 0, sizeof(a[i]));int loc = 10000000;int x,y;for (int i = 0; i < 4; ++i) {x = st/loc%10;loc /= 10;y = st/loc%10;loc /= 10;a[x][y] = 1;}
}void show(int a[][N]) {for(int i = 0; i < N; ++i) {for(int j = 0; j < N; ++j) printf("%d",a[i][j]);puts("");}puts("");
}
void show(int sta) {int a[N][N];itog(a, sta);show(a);
}void findadj (vector<int> &adj, const int fr) {adj.clear();int tmp[N][N];int ball[4][2];int loc = 10000000;for (int i = 0; i < 4; ++i) {ball[i][0] = fr/loc%10;loc /= 10;ball[i][1] = fr/loc%10;loc /= 10;}for(int i = 0; i < 4; ++i) {for(int j = 0; j < 4; ++j) {itog(tmp, fr);int x = ball[i][0] + godir[j][0];int y = ball[i][1] + godir[j][1];int flag = 1;if( 0 <= x && x < N && 0 <= y && y < N && tmp[x][y]!=1) {flag = 0;tmp[x][y] = 1;tmp[ball[i][0]][ball[i][1]] = 0;adj.push_back( gtoi(tmp) );}if(flag) {x = ball[i][0] + godir[j][0]*2;y = ball[i][1] + godir[j][1]*2;if( 0 <= x && x < N && 0 <= y && y < N && tmp[x][y]!=1) {tmp[x][y] = 1;tmp[ball[i][0]][ball[i][1]] = 0;adj.push_back( gtoi(tmp) );}}}}
}int dsbfs(int src, int des) {//传入起点状态，终点状态int dir = 0; // 表示方向 int e[2]; // 目标状态 queue<int> que[2]; // 队列（两个队列，0保存起始状态的搜索，1表示结束状态的搜索） /*dis 用来记录距离，由于状态只有8^8=16777216 个，但是为了方便，用到了8位十进制的整数来保存，这样就有10^8=100000000 个数了，内存肯定溢出所以用map来保存距离*/map<int, int> dis[2];vector<int> adj; // 寻找fr扩展的节点 e[0] = des, e[1] = src; // e表示dir应该搜索的目标//e[0]的目标为终点des，e[1]的目标表示为起点src//搜索0的搜索起点为src,搜索1的起点为desque[0].push(src), que[1].push(des);//初始化起点向终点搜索的起点为src步长为1,终点向起点的搜索起点为des步长为1dis[0][src] = 1, dis[1][des] = 1;/* 开始双向搜索啦，双向广搜 */while(!que[0].empty() || !que[1].empty()) {dir = que[0].size() <= que[1].size() ? 0 : 1; // 找节点少的队列进行扩展 ，减少复杂度if(que[dir].empty() && !que[!dir].empty()) dir = !dir; // 如果一个队列为空了就找剩下一个队列int fr = que[dir].front();//取出可以取出的头节点que[dir].pop();//并删除int frdis = dis[dir][fr];if(e[dir]==fr) { // 找到了对方 return frdis;}if(dis[!dir][fr]) { // 搜索到对方扩展的状态就可以返回了 return dis[!dir][fr] + frdis - 1;}findadj(adj, fr);for(int i = 0; i < adj.size(); ++i) {if(dis[dir][adj[i]]==0 && frdis + 1 <= 5) { // 己方搜索到的状态不会重复并且距离最短 dis[dir][adj[i]] = frdis + 1;que[dir].push(adj[i]);}}}return 0;
}int main () {int x, y;int src, des;//起点，终点状态while(scanf("%d", &x) - EOF) {// 第一个图的输入scanf("%d", &y);memset(g, 0, sizeof(g));g[x-1][y-1] = 1;for (int i = 0; i < 3; ++i) {scanf("%d%d", &x, &y);g[x-1][y-1] = 1;}src = gtoi(g);//通过已经得到的图状态来获得起点状态值memset(g, 0, sizeof(g));// 第二个图的输入for (int i = 0; i < 4; ++i) {scanf("%d%d", &x, &y);g[x-1][y-1] = 1;}des = gtoi(g);//得到得到第二个图的状态来得到终点状态值printf("%s\n", dsbfs(src, des)? "YES" : "NO");//如果8步之内发现两者相交，说明ok}return 0;
}