【一只蒟蒻的刷题历程】【蓝桥杯】历届试题九宫重排（八数码问题：BFS+集合set）-白红宇的个人博客

【一只蒟蒻的刷题历程】【蓝桥杯】历届试题九宫重排（八数码问题：BFS+集合set）

发布日期：2021-05-04 19:23:40 浏览次数：20 分类：技术文章

本文共 1664 字，大约阅读时间需要 5 分钟。

资源限制

时间限制：1.0s 内存限制：256.0MB

问题描述

如下面第一个图的九宫格中，放着 1~8 的数字卡片，还有一个格子空着。与空格子相邻的格子中的卡片可以移动到空格中。经过若干次移动，可以形成第二个图所示的局面。

我们把第一个图的局面记为：12345678.

把第二个图的局面记为：123.46758

显然是按从上到下，从左到右的顺序记录数字，空格记为句点。

本题目的任务是已知九宫的初态和终态，求最少经过多少步的移动可以到达。如果无论多少步都无法到达，则输出-1。

输入格式

输入第一行包含九宫的初态，第二行包含九宫的终态。

输出格式

输出最少的步数，如果不存在方案，则输出-1。

样例输入

在这里插入图片描述

样例输出

样例输入

在这里插入图片描述

样例输出

思路：

思路来自紫书P199页，一毛一样的题目。

通过BFS求最短路，第一次出现与目标九宫格相同时，就是最少的步数

把九宫格的状态通过数组记录下来，记录过程中需要判重，避免把同种情况的九宫格访问多次。

判重：将九宫格变化为一个九位数放入集合中（集合中没有才放入）。

看书上说集合这种方法虽然简单，但是效率最慢，以后有需要在学习其他几种方法。

memcmp

memcpy

代码：

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           using namespace std;typedef int state[9];string s1,s2;const int maxn=362900; //最大情况9！=362880state st[maxn],goal; //存过程的二维数组和目标数组，st相当于st[maxn][9]set
            
              s; //集合int dis[maxn]; //距离int dx[]={ 0,0,1,-1}; //四个方向int dy[]={ 1,-1,0,0};void init() { s.clear();} //初始化集合bool insert(int rear) //插入集合{ int v=0; for(int i=0;i<9;i++) v=v*10+st[rear][i]; //九宫格转变为九位数 if(s.count(v)>0) return 0; //s中有相同的，return 0 s.insert(v); return 1;}int bfs(){ init(); int front=1,rear=2; //如果要从0开始，最后可以用return -1表示不存在 while(front
             
              =0&&newx<3&&newy>=0&&newy<3) { state& r= st[rear]; //引用 memcpy(r,f,sizeof(f)); //扩展新节点(先和上一个状态一样) r[newz]=f[z]; //然后改变移动以后，变化的两个点 r[z]=f[newz]; dis[rear]=dis[front]+1; //更新步数 if(insert(rear)) rear++; //插入成功，队尾往后移 } } front++; //扩展完毕后修改队首指针 } return 0; //不存在}int main() { getline(cin,s1); //字符串输入，再转化为int数组 getline(cin,s2); for(int i=0;i<9;i++) { if(s1[i]=='.') st[1][i]=0; //起始状态 else st[1][i]=s1[i]-'0'; if(s2[i]=='.') goal[i]=0; //目标状态 else goal[i]=s2[i]-'0'; } int ans = bfs(); if(!ans) cout<<-1; else cout<

上一篇：win10连接上wifi显示无internet，并且wlan的属性都点不了，可尝试的解决方法（亲测有用！！！）

下一篇：【一只蒟蒻的刷题历程】【洛谷】 P1160-队列安排（链表插入和删除）

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

资源限制

问题描述

输入格式

输出格式

样例输入

样例输出

样例输入

样例输出

思路：

代码：

发表评论

最新留言

关于作者

推荐文章