【蓝桥杯冲冲冲】进阶搜索 八数码难题

蓝桥杯备赛 | 洛谷做题打卡day23

• 八数码难题

  题目描述

  在 $3\times 3$ 的棋盘上，摆有八个棋子，每个棋子上标有 $1$ 至 $8$ 的某一数字。棋盘中留有一个空格，空格用 $0$ 来表示。空格周围的棋子可以移到空格中。要求解的问题是：给出一种初始布局（初始状态）和目标布局（为了使题目简单,设目标状态为 $123804765$），找到一种最少步骤的移动方法，实现从初始布局到目标布局的转变。

输入格式

输入初始状态，一行九个数字，空格用 $0$ 表示。

输出格式

只有一行，该行只有一个数字，表示从初始状态到目标状态需要的最少移动次数。保证测试数据中无特殊无法到达目标状态数据。

样例 #1

样例输入 #1

283104765

样例输出 #1

4

提示

样例解释

图中标有 $0$ 的是空格。绿色格子是空格所在位置，橙色格子是下一步可以移动到空格的位置。如图所示，用四步可以达到目标状态。

并且可以证明，不存在更优的策略。

题解代码

学会利用新知，自己多试试并尝试积攒一些固定解答方案，debug，以下是题解代码 ~

#include<iostream>
#include<map>
#include<queue>
#include<algorithm>
#define ll long long//在这里看到一种很骚的操作：直接把int定义成long long；main函数用signed类型--麻麻再也不怕我忘开long long了！
using namespace std;
const ll dx[]={-1,0,0,1},dy[]={0,-1,1,0};//转移数组；
ll n;
int  main()
{
    cin>>n;
    queue<ll> q;
    q.push(n);
    map<ll,ll> m;
    m[n]=0;
    while(!q.empty())
    {
        int u=q.front(); //初始状态入队列
        int c[3][3],f=0,g=0,n=u;q.pop();
        if(u==123804765)break;
        for(ll i=2;i>=0;i--)
            for(ll j=2;j>=0;j--)
            {
                c[i][j]=n%10,n/=10;
                if(!c[i][j])f=i,g=j;
            }
        for(ll i=0;i<4;i++)
        {
            ll nx=f+dx[i],ny=g+dy[i],ns=0;
            if(nx<0||ny<0||nx>2||ny>2)continue; //越界就不执行
            swap(c[nx][ny],c[f][g]);
            for(ll i=0;i<3;i++)
                for(ll j=0;j<3;j++)ns=ns*10+c[i][j];//矩阵转数列 
            if(!m.count(ns))
            {
                m[ns]=m[u]+1;//map去重的同时顺便统计到达这个状态所需的步数
                q.push(ns);
            }
            swap(c[nx][ny],c[f][g]);//状态复原
        }
    }
    cout<<m[123804765]<<endl; // map的下标直接用数列表示
    return 0;
}

我的一些话

• 今天学习进阶搜索，深搜属于比较难的部分，需要多动脑，多思考思路还是很好掌握的，虽然一次性AC有一定难度，需要通盘的考虑和理解，以及扎实的数据结构基础才能独立写出AC代码。但无论难易，大家都要持续做题，保持题感喔！一起坚持(o´ω`o)

• 如果有非计算机专业的uu自学的话，关于数据结构的网课推荐看b站上青岛大学王卓老师的课，讲的很细致，有不懂都可以私信我喔

• 总结来说思路很重要，多想想，多在草稿纸上画画，用测试数据多调试，debug后成功编译并运行出正确结果真的会感到很幸福！

• 关于之前蓝桥杯备赛的路线和基本方法、要掌握的知识，之前的博文我都有写，欢迎大家关注我，翻阅自取哦~

• 不管什么都要坚持吧，三天打鱼两天晒网无法形成肌肉记忆和做题思维，该思考的时候一定不要懈怠，今天就说这么多啦，欢迎评论留言，一起成长：）