题目描述

八数码

样例

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int manx = 362900;
int start[9],goal[9];
int a[manx];
int dir[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
struct node{
    int state[9];     //记录每种状态 
    int dis;          //记录次数 
};

int fac[10];
void init(){ 
     //初始0~9的阶乘   
     fac[0] = fac[1] = 1;
     for(int i=2;i<=9;++i) fac[i] = fac[i-1]*i;
}

//康托展开 
int cantor(int s[],int n){
     int re = 0 ;
     for(int i=0;i<n;i++){
         int t = 0 ;
         for(int j=i+1;j<n;j++){
             if(s[i]>s[j])t++;
         }
         re = re+t*fac[n-i-1];
      }
      re = re+1;
      //判重 
      if(!a[re]){++a[re];return 1;}
      return 0;
}

bool check(int x , int  y){
     return x>=0&&x<3&&y>=0&&y<3;
}

int bfs(){
     cantor(start,9);
     node frist;
     queue<node> q;
     frist.dis=0;
     memcpy(frist.state,start,sizeof(start));
     q.push(frist);
     while(!q.empty()){
          node now = q.front();
          q.pop();
          int z = 0;
          for(;z<9;++z) if(now.state[z]==0) break;
          //得到空格子(0)的坐标 ：一维化二维 
          //例如3*3:0的坐标是(1,0) ,得到x=1，y=0 
          int x = z/3;
          int y = z%3;
          for(int i=0;i<4;i++){
              int nx = x+dir[i][0];
              int ny = y+dir[i][1];
              if(check(nx,ny)){
                  //二维化一维 
                  //0坐标的周围点在一维中的表示 ：xy 
                  int xy = ny+nx*3;  
                  node temp = now;
                  swap(temp.state[z],temp.state[xy]);
                  temp.dis++; 
                  if(memcmp(temp.state,goal,sizeof(goal))==0) return temp.dis;
                  //判重 
                  if(cantor(temp.state,9)) q.push(temp);
               }
           }
       }
       return -1;
}

int main(){
    init();
    for(int i=0;i<9;i++){
        char x;
        cin>>x;
        if(x=='x')start[i] = 0;
        else start[i] = x-'0';
    }
    for(int i=0;i<9;i++) goal[i] = (i+1)%9;
    int ans = bfs();
    cout<<ans<<endl;
}