题目链接
代码：
#include<stdio.h>
#include<iostream>
#include<map>
#include<queue>
using namespace std;
#define ll long long
ll dir[4][2]={
{0,1},{-1,0},{1,0},{0,-1}};int main()
{map<ll,int>vis;//1表示正向搜索过，2表示反向搜索过map<ll,string>line;//记录搜索的策略queue<ll>que;char ss[4];ss[0]='r';ss[1]='u';ss[2]='d';ss[3]='l';/*ss[4]为步骤，每次判定完将步骤加到搜索的策略里在反向搜索时，向右应该是向左向左应该是向右与正向搜索相反y+1,x不变为向右y-1,x不变为向左y不变,x+1为向下y不变,x-1为向上*/char c;ll end1=123456780,start1=0,nowx,nowy;//定义最终状态for(int i=0;i<9;++i){cin>>c;if(c<='9'&&c>='0')start1=start1*10+c-'0';elsestart1*=10;}//读入初始状态que.push(start1);que.push(end1);vis[start1]=1;vis[end1]=2;//将初始状态和最终状态放入队列中while(!que.empty())//双向bfs操作{ll now=que.front();que.pop();ll temp1=now;ll now1[3][3];for(int i=2;i>=0;--i)for(int j=2;j>=0;--j){now1[i][j]=temp1%10;temp1/=10;if(now1[i][j]==0){nowx=i;nowy=j;}}//取出当前状态值，存到3x3数组中for(int i=0;i<4;++i){ll nextx=nowx+dir[i][0];ll nexty=nowy+dir[i][1];if(nextx<0||nextx>2||nexty<0||nexty>2)continue;swap(now1[nextx][nexty],now1[nowx][nowy]);ll next1=0;for(int k=0;k<3;++k){for(int j=0;j<3;++j){next1=next1*10+now1[k][j];}}//求出next1值作为搜索的下一步if(vis[next1]==vis[now])//如果当前状态已经被访问过{swap(now1[nextx][nexty],now1[nowx][nowy]);continue;}if(vis[now]+vis[next1]==3)//如果为3说明正反搜索相遇{if(vis[now]==1)//vis[next1]==2,搜索步为反向搜索，先输出line[now]cout<<line[now]+ss[i]+line[next1]<<endl;else//vis[next1]==1,搜索步为正向搜索,先输出line[next1](搜索步){cout<<line[next1]+ss[3-i]+line[now]<<endl;}return 0;}vis[next1]=vis[now];//将搜索方向一致化if(vis[next1]==1)//如果搜索方向为正向{line[next1]=line[now]+ss[i];}else{//反向搜索时注意搜索策略与正向相反为ss[3-i]line[next1]=ss[3-i]+line[now];}que.push(next1);swap(now1[nextx][nexty],now1[nowx][nowy]);}}printf("unsolvable\n");return 0;
}