题目内容
解题思路
这明显看上去就是一道搜索题（确认）。
我们知道输入的是初状态，123804765是末状态，初末状态都已知，于是想到可以进行双向bfs，从初末状态同时进行两个方向的bfs，可近似将复杂度降低为开根号。
具体的思路是：在同一个队列里进行同时扩展，使用两个map分别储存步数和访问状态，其中vis存储状态，1为从头出发访问的，2为从末状态访问的；step存储步数。
开头时定义了一个board数组用来储存棋盘，定义了两个函数进行9位数码和棋盘的转换（encode(int)和decode()）。
每一次从队首取出一个数码时，先将其解压到board数组中方便操作，然后进行四个方向的扩展，将空格和其四个方向上的点进行交换，并使用chkboard()函数进行边界判断，在进行访问状态的判断，如果已经访问过了，就将正反向两次的步数加起来即为最终结果。
第一次写双向bfs，大佬勿喷
（真没想到这会是一道蓝题）
代码实现
#include <cstdio>
#include <queue>
#include <algorithm>
#include <map>
using namespace std;
int board[4][4];//存储棋盘使用
int nxt[4][2]={{1,0},{-1,0},{0,1},{0,-1}};//方向操作数组
map<int,int> vis;//1为正向访问，2为反向访问
map<int,int> step;//存储该状态的步数
inline int encode()//将board数组转为9位数码
{
int tmp=0;
for(int i=1;i<4;i++)
for(int j=1;j<4;j++)
{
tmp*=10;
tmp+=board[i][j];
}
return tmp;
}
inline void decode(int code)//将9位码存储进board数组
{
int tmp=1e8;
for(int i=1;i<4;i++)
for(int j=1;j<4;j++)
{
board[i][j]=code/tmp;
code%=tmp;
tmp/=10;
//printf("%d ",board[i][j]);
}
return;
}
inline void getxy(int &x0,int &y0)//取出空格的坐标
{
for(int i=1;i<4;i++)
for(int j=1;j<4;j++)
if(board[i][j]==0)
{
x0=i;
y0=j;
return;
}
}
inline bool chkboard(int x,int y)//判断边界
{
if(x<1||y<1||x>3||y>3)
return false;
return true;
}
int bfs(int fst)//bfs函数
{
queue<int> q;
q.push(fst);
q.push(123804765);//将始末状态都入队
vis[fst]=1;
step[fst]=0;
vis[123804765]=2;
step[123804765]=0;//对两个map进行初始化
while(!q.empty())
{
int cur=q.front();//取出队首元素
decode(cur);
q.pop();
int x0,y0;
getxy(x0,y0);//取出空格的位置
for(int k=0;k<4;k++)
{
int xx=x0+nxt[k][0],yy=y0+nxt[k][1];
if(!chkboard(xx,yy)) continue;//判断边界
swap(board[xx][yy],board[x0][y0]);//进行移动棋子操作
int now=encode();//将棋盘重新压回数码
if(vis[now]==vis[cur])//判重，与上次相同的直接跳过
{
swap(board[xx][yy],board[x0][y0]);//一定要换回去
continue;
}
if(vis[now]+vis[cur]==3)//如果发现此状态被对方访问过，直接出结果
{
return step[now]+step[cur]+1;
}
vis[now]=vis[cur];//否则继续bfs
step[now]=step[cur]+1;
q.push(now);
swap(board[xx][yy],board[x0][y0]);//换回去
}
}
return -1;//debug的时候用的
}
int main()
{
int fst;
#ifndef ONLINE_JUDGE
freopen("1379.in","r",stdin);//本地调试时使用
#endif
scanf("%d",&fst);
//printf("%d",fst);
if(fst==123804765)//特判测试点#31
{
printf("0\n");
return 0;
}
printf("%d\n",bfs(fst));
return 0;
}
反思：
第一次写双向bfs的题，注重在状态的表示，有HASH的思想，使用一个9位的数字可以很方便的表示并存储状态。
双向bfs可以节约大量时间。（我用单向bfs竟然T了两个点，迷惑）
留言