八数码裸bfs-白红宇

八数码裸bfs

阅读量：4454 次

发布时间：2019-06-07

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

#define DeBUG#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #include 
                  #include 
                   
                    #include
                    
                     using namespace std ;#define zero {0}#define INF 2000000000#define EPS 1e-6typedef long long LL;const double PI = acos(-1.0);inline int sgn(double x){ return fabs(x) < EPS ? 0 :(x < 0 ? -1 : 1);}int n;//n*n struct MAP{ int mp[10][10];//状态 int step[100];//回溯方向 int stepnum;//步数 int x,y;//保存当前0位置 inline bool operator ==(const MAP &a) { for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) { if(mp[i][j]!=a.mp[i][j]) return false; } return true; }};MAP origin;//初始态 MAP goal;int dir[4][2]= { 0,1,0,-1,-1,0,1,0};void Reset(){ memset(origin.mp,-1,sizeof(origin.mp)); int num=1; for(int i=1; i<=n; i++) { for(int j=1; j<=n; j++) { origin.mp[i][j]=num++; } } origin.mp[n][n]=0; origin.x=n; origin.y=n; memset(origin.step,-1,sizeof(origin.step)); origin.stepnum=0;}int maxx=1;MAP bfs(){ queue
                     Q; Q.push(origin); MAP now; int m,k; while(!Q.empty()) { now=Q.front(); Q.pop(); int len=now.stepnum; // printf("%d %d\n",len+1,maxx++); m=now.y; k=now.x; for(int l=0; l<4; l++) { if((l==0&&now.step[len-1]==1)|| (l==1&&now.step[len-1]==0)|| (l==2&&now.step[len-1]==3)|| (l==3&&now.step[len-1]==2)) continue; int ni=m+dir[l][0]; int nj=k+dir[l][1]; if(now.mp[ni][nj]>=0) { swap(now.mp[m][k],now.mp[ni][nj]); now.step[now.stepnum++]=l; now.x=nj; now.y=ni; if(now==goal) { // printf("%d\n",now.stepnum); // printf("Time used = %.0lf ms\n",(double)(1000*clock()/CLOCKS_PER_SEC));//********************** // system("pause"); return now; } else { Q.push(now); now.x=k; now.y=m; now.stepnum--; now.step[len]=-1; swap(now.mp[m][k],now.mp[ni][nj]); } } } } printf("%d\n",now.stepnum); return now;}int main(){#ifdef DeBUGs freopen("C:\\Users\\Sky\\Desktop\\1.in","r",stdin); // freopen("C:\\Users\\Sky\\Desktop\\打表.txt","w",stdout);//PLEASE DELETE IT!!!!!!!!!!!!!!!!!!!!!!!!#endif while(scanf("%d", &n)+1) { MAP it; Reset(); for(int i=1; i<=n; i++) { for(int j=1; j<=n; j++) { scanf("%d", &goal.mp[i][j]); } } it=bfs(); printf("%d\n",it.stepnum); for(int i=it.stepnum-1;i>=0;i--) { switch(it.step[i]) { case 0: printf("l"); break; case 1: printf("r"); break; case 2: printf("d"); break; case 3: printf("u"); break; default: printf("kao"); } } printf("\n"); } return 0;}/*35 1 34 2 60 7 836 2 81 0 34 7 532 7 31 8 45 0 637 5 31 0 42 8 633 4 10 2 67 5 833 1 52 0 84 7 631 5 27 4 80 6 334 0 85 6 17 3 234 5 02 3 17 8 632 6 84 5 71 3 031 2 34 5 67 0 88uurdldrr16rullddrrulurdldr13uuldrrdllurdr20rdlulurdldrulurdldrr15urrdllurdrulddr14uldrrullddrurd10urrdluurdd17rddluurddlulurrdd12dlurdllurdrd20uldruuldldrruulldrdr1r请按任意键继续. . .*/