洛谷1379八数码难题
题目描述
在3×3的棋盘上，摆有八个棋子，每个棋子上标有1至8的某一数字。棋盘中留有一个空格，空格用0来表示。空格周围的棋子可以移到空格中。要求解的问题是：给出一种初始布局（初始状态）和目标布局（为了使题目简单,设目标状态为123804765），找到一种最少步骤的移动方法，实现从初始布局到目标布局的转变。
输入输出格式
输入格式：
输入初试状态，一行九个数字，空格用0表示
输出格式：
只有一行，该行只有一个数字，表示从初始状态到目标状态需要的最少移动次数(测试数据中无特殊无法到达目标状态数据)
输入输出样例
输入样例#1：
283104765
输出样例#1：
4
#include<iostream> #include<cstdio> #include<cstring> #include<map> #include<queue> using namespace std; string st,aim=" 123804765",s,si; char x; map<string,int>p; queue<string>q; queue<int>t; int main() { cin>>st; st=' '+st; q.push(st); p[st]=1; t.push(0); while(!q.empty()) { s=q.front(); int step=t.front(); t.pop();q.pop(); if(s==aim) { cout<<step<<endl; return 0; } si=s; int pi=si.find("0"); if(pi+3<=9) { x=si[pi+3];si[pi+3]=si[pi];si[pi]=x; if(p[si]==0) { q.push(si);t.push(step+1); p[si]=1; } } si=s; if(pi-3>=1) { x=si[pi-3];si[pi-3]=si[pi];si[pi]=x; if(p[si]==0) { q.push(si);t.push(step+1); p[si]=1; } } si=s; if(pi+1<=9&&pi!=3&&pi!=6) { x=si[pi+1];si[pi+1]=si[pi];si[pi]=x; if(p[si]==0) { q.push(si);t.push(step+1); p[si]=1; } } si=s; if(pi-1>=1&&pi!=7&&pi!=4) { x=si[pi-1];si[pi-1]=si[pi];si[pi]=x; if(p[si]==0) { q.push(si);t.push(step+1); p[si]=1; } } } }
/*八个数码可能构成的状态共有9！=362880种情况，可以用宽搜的方法，每种状态用一个九位的int来存储，并确保无重复，需要开bool数组来对各种状态进行标记。于是10^8这样大的数组是空间复杂度难以接受。 而如果将八数码的所有状态合看作是一个全排列，每一种状态都是一种排列，就可以用康托展开来压缩所有状态，只需开一个大小为9！=362880的数组来存储是否出现重复情况即可。 然后康托展开求阶乘没必要一个一个循环，可以用秦九韶算法 4*4!+2*3!+2*2!=113 (((4*4+2)*3+2)*2+1)*1=113 Have[ ][ ]存储某种状态是否存在 Line[ ][ ]存储双向宽搜的状态 Last[ ][ ]存储上一种状态的编号，用来输出路径 Len[ ]存储双向宽搜的已有状态数 Mid[ ]找到的答案 Now[ ]存储当前搜索到的八数码的状态 Line[0][ ]和line[1][ ]分别为两条队列 Line[0][now[0]]，Line[1][now[1]]为队列的首元素 Line[0][len[0]]，Line[1][len[1]]为队列尾元素*/ #include<iostream> #include<cstdio> using namespace std; #define MAXN 370000 int s[10],line[2][MAXN],len[2],now[2],have[2][MAXN],mid[2],last[2][MAXN],NUM; int p; int turn(){ int result=0; for(int i=0;i<9;i++){ result*=10; result+=s[i]; } return result; } int cantor(){ int a=0,b=0; for(int i=8;i>=1;i--){//从后往前枚举每个数 int b=s[i]; for(int j=8;j>i;j--){//枚举这个数后面的数 if(s[j]<s[i])--b; } a+=b; a*=i; } return a; } void get(int num){ for(int i=8;i>=0;i--){ s[i]=num%10; if(s[i]==0)p=i; num/=10; } } void go(int c,int w){ int temp=0,num=0; temp=s[p];s[p]=s[p+c];s[p+c]=temp; ++len[w]; line[w][len[w]]=turn(); num=cantor(); if(have[w][num]!=0)--len[w]; else{ last[w][len[w]]=now[w]; if(have[!w][num]!=0){ mid[w]=len[w]; mid[!w]=have[!w][num]; } else have[w][num]=len[w]; } temp=s[p];s[p]=s[p+c];s[p+c]=temp; } void out(){ NUM++; /*int cnt=0; for(int i=1;i<=3;i++){ for(int j=1;j<=3;j++){ cout<<s[cnt];cnt++; }cout<<endl; } cout<<endl;*/ } void out1(int num){ if(num!=1){ out1(last[0][num]); //cout<<" "; } get(line[0][num]); out(); } void out2(int num){ get(line[1][num]); if(num!=mid[1]) out(); if(num!=1){ //cout<<" "; out2(last[1][num]); } } int main(){ char ch[10]; cin>>ch; for(int i=0;i<9;i++) s[i]=ch[i]-'0'; int shu=turn(); int kang=cantor(); line[0][1]=shu;//正向bfs的第一个状态是初始状态 len[0]=1;now[0]=1;have[0][kang]=1; s[0]=1;s[1]=2;s[2]=3;s[3]=8;s[4]=0;s[5]=4;s[6]=7;s[7]=6;s[8]=5; shu=turn(); kang=cantor(); line[1][1]=shu;//反向bfs的第一个状态是目标状态 len[1]=1;now[1]=1; if(have[0][kang]==0)have[1][kang]=1; else{ cout<<0<<endl; } while(mid[0]==0&&(now[0]<=len[0]||now[1]<=len[1])){//还没出答案，继续搜 while(mid[0]==0&&len[1]>=len[0]&&now[0]<=len[0]){//反向bfs的状态数多于正向bfs，就着手正向bfs get(line[0][now[0]]); //讨论0的位置 if(p>=3&&mid[0]==0)go(-3,0);//在后两行，可以上移 if(p<=5&&mid[0]==0)go(3,0);//在前两行，可以下移 if(mid[0]==0&&p>=1&&(p-1)%3!=2)go(-1,0);//在右两列，可以左移 if(mid[0]==0&&p<=8&&(p+1)%3!=0)go(1,0);//在左两列，可以右移 ++now[0]; } while(mid[0]==0&&len[0]>=len[1]&&now[1]<=len[1]){ get(line[1][now[1]]); if(p>=3&&mid[1]==0)go(-3,1); if(p<=5&&mid[1]==0)go(3,1); if(mid[1]==0&&p>=1&&(p-1)%3!=2)go(-1,1); if(mid[1]==0&&p<=8&&(p+1)%3!=0)go(1,1); ++now[1]; } } out1(mid[0]); out2(mid[1]); cout<<NUM-1; }