算法竞赛入门到进阶之八数码问题模板

/*
BFS+Cantor()模板 解决八数码,十六数码问题. 
*/
#include<bits/stdc++.h>
const int LEN = 362880;
using namespace std;
struct node{
  int state[9];
  int dis;
};
int dir[4][2] = {{-1,0},{1,0},{0,1},{0,-1}};//上下,右左四个方向
int visited[LEN] = {0};//每个状态对应的记录, 用于标记是否
int start[9];//开始状态 
int goal[9]; //目标状态
long int factory[] = {1,1,2,6,24,120,720,5040,40320,362880};//Cantor()用到的常数==> 0!~9! 
int Cantor(int str[],int n){//用康拓展开来判重 
  long result = 0;//str排在第几位 
  for(int i = 0; i < n; i++){
    int counted = 0;
    for(int j = i+1;j < n; j++){
      if(str[i]>str[j]){
        counted++;//当前未出现的元素排在第几位 
      }
    }
    result+=counted * factory[n-i-1]; 
  } 
  if(!visited[result]){//没有被访问过 
    visited[result] = 1;
    return 1;
  }else{
    return 0;
  } 
} 
int bfs(){
  node head;//用于存放起始点 
  memcpy(head.state,start,sizeof(head.state)); // memcpy(void *dest, void *src, int count) 由src所指内存区域复制count个字节到dest所指内存区域。
  head.dis = 0;
  queue<node> q;
  Cantor(head.state,9);//标记起点 已经被访问过. 
  q.push(head);//进队列
  while(!q.empty()){
    head = q.front();
    q.pop(); 
    if(memcmp(head.state,goal,sizeof(goal))==0){
      return head.dis;//到达目标状态,结束 
    }
    int z;
    for(z = 0;z < 9;z++){//找这个状态中元素0的位置 
      if(head.state[z]==0){
        break;
      }
    }
    //转换为二维,左上角是 (0,0)
    int y = z %3;
    int x = z / 3; 
    for(int i = 0; i < 4;i++){
      int newX = x+dir[i][0];//元素0 转移后的新坐标 
      int newY = y + dir[i][1];
      int nz = newX*3+newY;
      if(newX>=0&&newX<3&&newY>=0&&newY<3){//判断是否越界 
        node newnode;
        memcpy(&newnode,&head,sizeof(struct node));// 用head对newnode进行初始化
        swap(newnode.state[z],newnode.state[nz]);// 把0移动到新的位置
        newnode.dis++;
        if(Cantor(newnode.state,9)){//判断是否被访问过 
          q.push(newnode);//将其放入到队列中 
        } 
        //把0转移到新的位置. 
      }
    }
  } 
  return -1;//没找到 
} 
int main()
{
  for(int i = 0;i <9;i++){
    cin>>start[i];
  } 
  for(int i = 0;i <9;i++){
    cin>>goal[i];
  } 
  int num = bfs();
  cout<<num<<endl;
  return 0;
}
//1 2 3 0 8 4 7 6 5
//1 0 3 8 2 4 7 6 5