题目描述

在一个3*3的棋盘上放置编号为1-8的8个方块，每个占一格，另外还有一个空格。与空格相邻的数字方块可以移动到空格里。任务1：指定初始棋局和目标棋局，计算出最少的移动步数；任务2：输出数码的移动序列。
把空格看成0，一共有9个数字。
输入样例：

1 2 3 0 8 4 7 6 5
1 0 3 8 2 4 7 6 5

输出样例:

2

题目分析

这里先解决任务1，任务2是在任务1的基础上通过标记序列和回溯去解决的。
把一个棋局看成一个状态图，总共有9！= 362880个状态。从初始棋局开始，每次移动转到下一个状态，到达目标棋局停止。八数码问题其实是一个经典的BFS问题。八数码从初始状态出发，每次转移逐步逼近目标状态。每转移一次，步数加1，当达到目标时，经过的步数就是最短路径。

八数码的重要问题其实是判重。对于已经访问过的状态要进行标记，防止重复访问。这里可以用数学方法“康托展开”来判重。
至于“康托展开”是什么，可以参考以下博客。
都能看懂的康托展开

代码：

#include<bits/stdc++.h>
using namespace std;
const int LEN=362880;
struct node{
	int state[9];//记录一个八数码排列，即一个状态
	int dis;//记录到起点的距离
};
int dir[4][2]={
	{-1,0},
	{0,-1},
	{1,0},
	{0,1}
};//左、上、右、下的顺时针方向
int vis[LEN];
int start[9],goal[9];
long int factory[]={1,1,2,6,24,120,720,5040,40320,362880};//0-9的阶乘
//用康托展开判重
int Cantor(int str[],int n)
{
	long result;
	for(int i=0;i<n;i++){
		int count=0;
		for(int j=i+1;j<n;j++){
			if(str[i]>str[j]) 
			count++;
		}
		result+=count*factory[n-i-1];
	}
	if(!vis[result]){
		vis[result]=1;
		return 1;
	}
	else
		return 0;
}
int bfs()
{
	queue<node> Q;
	node head;
	head.dis=0;
	//复制起点的状态
	memcpy(head.state,start,sizeof(head.state));
	if(Cantor(head.state,9))
	Q.push(head);
	while(!Q.empty()){
		head=Q.front();
		//到达目标，返回距离
		if(memcmp(head.state,goal,sizeof(goal))==0){
			return head.dis;
		}
		Q.pop();
		int z;
		//找到0的位置
		for(z=0;z<9;z++){
			if(head.state[z]==0){
				break;
			}
		}
		int x,y;
		//横、纵坐标
		x=z%3;y=z/3;
		for(int i=0;i<4;i++){
			int newx,newy;
			newx=x+dir[i][0];
			newy=y+dir[i][1];
			//转为一维
			int nz=newy*3+newx;
			if(newx>=0&&newx<3&&newy>=0&&newy<3){//未越界
				node newnode;
				memcpy(&newnode,&head,sizeof(struct node));
				//把0移动到新的位置
				swap(newnode.state[z],newnode.state[nz]);
				newnode.dis++;
				if(Cantor(newnode.state,9)){
					Q.push(newnode);
				}	
			}
		}
	}
	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();
	if(num!=-1) cout<<num<<endl;
	else cout<<"Impossible"<<endl;
	return 0;
}