题目内容

P1379

解题思路

这明显看上去就是一道搜索题(确认)。

我们知道输入的是初状态,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了两个点,迷惑)

最后修改日期:2020年2月25日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。