1571.八数码
时限：5000ms 内存限制：20000K 总时限：10000ms
描述
在九宫格里放在1到8共8个数字还有一个是空格，与空格相邻的数字可以移动到空格的位置，问给定的状态最少需要几步能到达目标状态（用0表示空格）：
1 2 3
4 5 6
7 8 0
输入
输入一个给定的状态。
输出
输出到达目标状态的最小步数。不能到达时输出-1。
10月27日第二版代码（比较简洁）：
#include <iostream>
#include <queue>
#include <map>
using namespace std;
struct node
{
int a[3][3];
int zx,zy; //0的位置
int digit; //把9个数字映射成九位整数，用来判重
bool useful; //该节点是否有效
}; //无效条件：0位置越界、节点重复
node start;
queue <node> q1;
map <int, int> used;
map <int, int> step;
int walk[4][2]=
{
0, -1,
+1, 0,
0, +1,
-1, 0
};
void input();
int setdigit(node n1); //将九个格内数字组合成九位整数
int bfs();
node moveto(node cur, int i); //返回节点cur扩展的新节点next
int main()
{
input();
cout<<bfs()<<endl;
return 0;
}
void input()
{
for(int i=0; i<3; i++)
{
for(int j=0; j<3; j++)
{
cin>>start.a[i][j];
if(start.a[i][j]==0)
{
start.zx=i;
start.zy=j;
}
}
}
start.digit=setdigit(start);
//标记初始数组并入队
used[start.digit]=1;
step[start.digit]=0;
q1.push(start);
}
//将九个格内数字组合成九位整数
int setdigit(node n1)
{
n1.digit=0;
for(int i=0; i<3; i++)
{
for(int j=0; j<3; j++)
{
n1.digit*=10;
n1.digit+=n1.a[i][j];
}
}
return n1.digit;
}
int bfs()
{
node cur,next;
while(!q1.empty())
{
cur=q1.front();
q1.pop();
int newx, newy;
for(int i=0; i<4; i++) //将0与四个方向上的数字交换
{
next=moveto(cur, i); //返回交换后的新节点next
if(next.useful) //若节点有效
{
if(next.digit==123456780) //判断是否到达目标状态
{
return step[next.digit];
}
else //未到达则入队
{
q1.push(next);
}
}
}
return -1;
}
//返回节点cur扩展的新节点next
//节点无效条件：越界、重复
node moveto(node cur, int i)
{
node next;
next.useful=false; //初始时设该节点无效
//复制一下cur的九个数字
for(int j=0; j<3; j++)
{
for(int k=0; k<3; k++)
{
next.a[j][k]=cur.a[j][k];
}
}
//计算0的新位置
newx=cur.zx+walk[i][0];
newy=cur.zy+walk[i][1];
//判断不越界
if(newx>=0&&newx<3&&newy>=0&&newy<3)
{
//将旧位置上的数字（0）与新位置上的数字交换
swap(next.a[cur.zx][cur.zy], next.a[newx][newy]);
next.zx=newx;
next.zy=newy;
next.digit=setdigit(next);
//判断不重复
if(!used.count(next.digit))
{
//标记节点到达，以及节点步数
used[next.digit]=1;
step[next.digit]=step[cur.digit]+1;
//标记该节点有效
next.useful=true;
}
}
return next;
}
【10月27日后记】
1.关于map判重，在这篇文章里有讲到 https://blog.csdn.net/qq_41727666/article/details/83004756
2.每个八数码状态的编码方法如下图所示，判重时要用到：
3.CSDN保存文章的时候居然会卡住？？？然后只能刷新重新写？？？
4.刚看了第四范式秋招疑似毁约，虽然挺败好感，但是CEO在知乎的回应感觉挺诚恳的，15年国外互联网公司纷纷开始缩小规模，16年开始国内各大厂纷纷紧跟缩招，倒是不担心应届生找工作，怕就怕三十啷当一把年纪还秃头挤完了奶和血背着房贷拖家带口老人看病孩子上学的时候就被公司辞退掉。这充分说明了低端码农接近饱和，人口红利逐渐吃完，行业迅速发展带来的普遍过高薪资逐渐回归传统行业分布，以后大厂怕是只要便宜好用的应届生和贼牛逼的技术专家了。不过中国生育率也蹭蹭下降，一方面缺少劳动力，另一方面也缺少韭菜了emmmm有点慌慌的，然而我离毕业工作还有五年orz，希望那个时候AI还没有过气QAQ……
10月12日第一版代码（有些冗余）：
#include <iostream>
#include <queue>
#include <map>
using namespace std;
struct node
{
int a[3][3]; //存储八数码
int zx,zy; //0的位置
int num; //将每个八数码状态转换成九位整数（最大为9876543210，int范围足够）
};
node target; //存储目标状态
queue <node> q1; //广搜所用队列
map <int, int> used; //判重
map <int, int> step; //存储步数
int bfs(); //广搜
node setnum(node n1); //计算n1.num
bool canmoveto(node n1, int d); //判断越界或重复
node moveto(node n1, int d); //返回新状态
bool totarget(node n1); //判断是否到达目标状态
int main()
{
node start; //输入初始状态
for(int i=0; i<3; i++)
{
for(int j=0; j<3; j++)
{
cin>>start.a[i][j];
if(start.a[i][j]==0) //记录0的位置
{
start.zx=i;
start.zy=j;
}
}
}
start=setnum(start); //计算start.num
//初始节点入队，并更新used和step数组
q1.push(start);
//cout<<used[start.num]<<endl;
used[start.num]=1;
step[start.num]=0;
//设定目标状态
int k=1;
for(int i=0; i<3; i++)
{
for(int j=0; j<3; j++)
{
target.a[i][j]=k;
k++;
}
}
target.a[2][2]=0;
//进行广搜
cout<<bfs()<<endl;
return 0;
}
int bfs()
{
node top,next;
while(!q1.empty())
{
top=q1.front();
//cout<<"gettop:"<<top.num<<endl;
q1.pop();
for(int d=0; d<4; d++) //将0与四个方向上的数字交换，0==左，1==下，2==右，3==上
{
if(canmoveto(top, d)) //判断重复和越界
{
next=moveto(top, d); //获得新状态
if(totarget(next)) //到达目标状态则返回
{
return step[next.num];
}
else //没到达目标状态则入队
{
q1.push(next);
/*
cout<<step[next.num]<<endl;
cout<<"push"<<next.num<<endl;
*/
}
}
}
}
return -1;
}
//计算n1.num
node setnum(node n1)
{
n1.num=0;
for(int i=0; i<3; i++)
{
for(int j=0; j<3; j++)
{
n1.num*=10; //将九个格内数字组合成九位整数
n1.num+=n1.a[i][j];
}
}
return n1;
}
//返回false条件：越界、重复
bool canmoveto(node n1, int d)
{
node n2; //先建立一个新节点，复制n1的状态
for(int i=0; i<3; i++)
{
for(int j=0; j<3; j++)
{
n2.a[i][j]=n1.a[i][j];
}
}
n2.zx=n1.zx;
n2.zy=n1.zy;
n2.num=n1.num;
switch(d)
{
case 0: //判断能否将0与左边数字交换
{
if(n2.zy==0) //越界
return false;
else
{
swap(n2.a[n2.zx][n2.zy],n2.a[n2.zx][n2.zy-1]); //将0与左边数字交换
n2.zy--; //更新0的位置
break;
}
}
case 1: //下
{
if(n2.zx==2)
return false;
else
{
swap(n2.a[n2.zx][n2.zy],n2.a[n2.zx+1][n2.zy]);
n2.zx++;
break;
}
}
case 2: //右
{
if(n2.zy==2)
return false;
else
{
swap(n2.a[n2.zx][n2.zy],n2.a[n2.zx][n2.zy+1]);
n2.zy++;
break;
}
}
case 3: //上
{
if(n2.zx==0)
return false;
else
{
swap(n2.a[n2.zx][n2.zy],n2.a[n2.zx-1][n2.zy]);
n2.zx--;
break;
}
}
}
n2=setnum(n2);
/*
cout<<d<<' '<<n2.num<<endl;
cout<<used.count(n2.num)<<endl;
*/
if(used.count(n2.num)!=0) //判重，重复返回false
{
//cout<<"chongfu"<<endl;
return false;
}
else
{
return true;
}
}
//返回新状态
node moveto(node n1, int d)
{
node n2;
for(int i=0; i<3; i++)
{
for(int j=0; j<3; j++)
{
n2.a[i][j]=n1.a[i][j];
}
}
n2.zx=n1.zx;
n2.zy=n1.zy;
n2.num=n1.num;
switch(d)
{
case 0: //将0与左边数字交换
{
swap(n2.a[n2.zx][n2.zy],n2.a[n2.zx][n2.zy-1]);
n2.zy--;
break;
}
case 1: //下
{
swap(n2.a[n2.zx][n2.zy],n2.a[n2.zx+1][n2.zy]);
n2.zx++;
break;
}
case 2: //右
{
swap(n2.a[n2.zx][n2.zy],n2.a[n2.zx][n2.zy+1]);
n2.zy++;
break;
}
case 3: //上
{
swap(n2.a[n2.zx][n2.zy],n2.a[n2.zx-1][n2.zy]);
n2.zx--;
break;
}
}
n2=setnum(n2);
//更新used数组，n2状态已用过
used[n2.num]=1;
//更新step数组，到达n2状态步数=1+到达n1状态步数
step[n2.num]=step[n1.num]+1;
//返回新状态n2
return n2;
}
//判断是否到达目标状态
bool totarget(node n1)
{
for(int i=0; i<3; i++)
{
for(int j=0; j<3; j++)
{
if(n1.a[i][j]!=target.a[i][j])
{
return false;
}
}
}
return true;
}
【后记】
1.写的时候出了个bug，把0和相邻数字交换位置后忘了更新0的新位置。
版权声明：本文为qq_41727666原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。