1571.八数码

本文主要是介绍1571.八数码，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

#include<iostream>
#include<queue>
#include<map>using namespace std;int num;
int istate;
int bs[3][3]; 
int sa[3][3];  //将sa也定义为全局变量的目的是简化程序，canmoveto 和moveto 函数都需要将u转化为二维数组，可以直接沿用
int brow,bcol;
int dr[4]={0,1,0,-1};
int dc[4]={-1,0,1,0};queue<int>q;
map<int,int>step;  //用来记录步数
map<int,int>isnew;  //用来标志已经出现的数void readdata();
void init();
int bfs();
int canmoveto(int u,int dire);
int moveto(int u,int dire);int main()
{readdata();init();num=bfs();cout<<num<<endl;
}int bfs()
{int u,v,i;while(!q.empty()){u=q.front();q.pop();for(i=0;i<4;i++)  // 0 1 2 3表示左下右上四个方向{if(canmoveto(u,i)) //如果可以挪动，即数组不越界{v=moveto(u,i);if(v==123456780){return(step[u]+1);}if(isnew[v]!=1){q.push(v); //将v加入到队列中isnew[v]=1;// 标志v已出现过step[v]=step[u]+1;//记录到达v的最小步骤 }}}}return (-1);  //如果不能挪动，则返回-1
}void readdata()
{int i,j,temp=0;for(i=0;i<3;i++){for(j=0;j<3;j++){cin>>bs[i][j];temp=temp*10+bs[i][j];  //将数组转化为一个数}}istate=temp;
}void init()
{q.push(istate);// 将初始值加入到队列中 isnew[istate]=1;//标志初始值已出现过step[istate]=0;//初始值的最小步数为0； 
}int canmoveto(int u,int dire)
{int i,j;for(i=2;i>=0;i--)  //将u转化为二维数组{for(j=2;j>=0;j--){sa[i][j]=u%10;u=u/10;if(sa[i][j]==0){brow=i;bcol=j;}}}if(dire==0&&bcol==0)  //判断四种情况下数组是否越界；越界则返回0{return(0);}if(dire==1&&brow==2){return(0);}if(dire==2&&bcol==2){return(0);} if(dire==3&&brow==0){return(0);}return(1);  //不越界则返回1
}int moveto(int u,int dire)
{int r,c;int i,j;int temp=0;r=brow+dr[dire];  //r c表示即将要挪动的位置的行列c=bcol+dc[dire];sa[brow][bcol]=sa[r][c];  //交换数值sa[r][c]=0;for(i=0;i<3;i++)  //将二维数组重新转化为整数{for(j=0;j<3;j++){temp=temp*10+sa[i][j];}}return(temp);
}

1571.八数码

时限：5000ms 内存限制：20000K  总时限：10000ms

这篇关于1571.八数码的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---