poj 1077--Eight（八數位問題，BFS+康托展開+路徑列印）

題意：經典的八數位問題，題目已确定好目标狀态，若從起始狀态到目标狀态有解，輸出最短的到達路徑的每一步操作；否則輸出unsolvable。

思路：這是一道經典的八數位問題，采用BFS+康托展開判重，主要多了一步列印路徑，把可變化位置x看成數字0放置位置，共有9個數字，即9!種狀态，在數組可開的範圍内，用pre結構體記錄目前狀态的前驅狀态即轉化過來的方式，再用棧倒過來列印答案即可。（BFS時用STL中的queue會逾時…故得手寫隊列，順便手寫了棧）

代碼如下：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=362880;//9!(把空位置x看成數字0)
char op[]={'u','d','l','r'};//上,下,左,右; 
int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};//方向數組要與op[]對應,便于操作; 
struct node
{
	int state[9];
	int step;
	int id;
};
struct pre//存前驅節點的标号和從前驅節點到目前節點的操作下标; 
{
	int id;
	int operation;
}pre[maxn+10];
bool vis[maxn+10]; 
int start[9],target[9];//起始狀态,終止狀态; 
int fac[]={1,1,2,6,24,120,720,5040,40320,362880};//階乘表(0~9);
node que[maxn*2];
int sta[maxn+10];
int front,rear;//隊頭,隊尾指針; 
int top;//棧頂指針; 
 
bool Cantor(int str[],int n)//康托展開判重; 
{
	int result=0;
	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*fac[n-i]);
	}
	if(!vis[result])
	{
		vis[result]=true;
		return true;//表示還沒走過; 
	}
	else
	{
		return false;
	}
} 

void get_ans(node now)
{	
	int pos=now.id;
	while(pre[pos].id!=-1)
	{
		sta[top++]=pre[pos].operation;
		pos=pre[pos].id;
	}
	
	while(top!=0)
	{
		int now=sta[--top];
		printf("%c",op[now]);
	}
	printf("\n");
}
 
void bfs()
{
	node s;
	memcpy(s.state,start,sizeof(s.state));
	s.id=0;
	pre[s.id].id=-1;
	pre[s.id].operation=-1;
	s.step=0;
	Cantor(s.state,8);
	que[rear++]=s;
	int pos=0;//枚舉目前是第幾個狀态,便于回溯列印路徑; 
	
	while(front<rear)
	{
		node now=que[front++];
		if(memcmp(now.state,target,sizeof(target))==0)//成功; 
		{
			get_ans(now);
			return ;
		}
		int i;
		for(i=0;i<=8;i++)//找可轉移狀态的點0; 
		{
			if(now.state[i]==0)
			{
				break;
			}
		}
		//轉化成3*3矩陣,左上角為(0,0); 
		int x=i/3;
		int y=i%3;
		for(int j=0;j<4;j++)
		{
			node in;
			int dx=x+dir[j][0];
			int dy=y+dir[j][1];
			if(dx<0||dx>=3||dy<0||dy>=3) continue;
			
			int where=dy+3*dx;//轉化為一維;
			memcpy(in.state,now.state,sizeof(in.state));
			swap(in.state[where],in.state[i]);
			in.step=now.step+1;
			
			if(Cantor(in.state,8))//判重 
			{
				in.id=(++pos);
				pre[in.id].id=now.id;
				pre[in.id].operation=j;
				que[rear++]=in;	
			} 
		}
	}
	printf("unsolvable\n");
} 
 
int main()
{
	int i,j;
	for(i=0;i<=8;i++)
	{
		char c[2];
		scanf("%s",c);
		if(c[0]>='0'&&c[0]<='9')
		{
			start[i]=c[0]-'0';
		}
		else
		{
			start[i]=0;
		}
	}
	for(i=0;i<=8;i++)//構造終止狀态; 
	{
		if(i!=8)
		{
			target[i]=i+1;
		}
		else
		{
			target[i]=0;
		}
	}
	memset(vis,false,sizeof(vis));
	front=rear=0;
	top=0;
	bfs();
	return 0;
 }