历届试题 九宫重排 (bfs 康托判重)

问题描述

　　如下面第一个图的九宫格中，放着 1~8 的数字卡片，还有一个格子空着。与空格子相邻的格子中的卡片可以移动到空格中。经过若干次移动，可以形成第二个图所示的局面。

　　我们把第一个图的局面记为：12345678.
　　把第二个图的局面记为：123.46758
　　显然是按从上到下，从左到右的顺序记录数字，空格记为句点。
　　本题目的任务是已知九宫的初态和终态，求最少经过多少步的移动可以到达。如果无论多少步都无法到达，则输出-1。

输入格式

　　输入第一行包含九宫的初态，第二行包含九宫的终态。

输出格式

　　输出最少的步数，如果不存在方案，则输出-1。

样例输入

12345678.
123.46758

样例输出

3

样例输入

13524678.
46758123.

样例输出

22

这道题在寒假的时候就想做了,但那时候啥都不会,现在终于自己写出来,算是把寒假时候的愿望实现了.上午写的2*3格子移字母

和这个也类似

#include<iostream>    
#include<string.h>  
#include<cstdio>
#define M 1000000  
using namespace std; 
typedef int type[9];
type qs,mb,gc[M];
int sept[M]; //保存步数 
int dir[4][2] = {-1,0,0,-1,0,1,1,0},st=0; 
int step[M]={0};
int fact[10]={1},vis[M];
void init() //初始化 阶乘 
{
	int i;
	for (i=1; i<=9; i++)
	{
		fact[i] = i*fact[i-1];
	}
}
int kangtuo(int *a)
{
	int num=0,t,i,j;
	for (i=0; i<8; i++)
	{
		t = 0;
		for (j=i+1; j<9; j++)
		{
			if (a[i] > a[j])
			t++;
		}
		num += t * fact[8-i];//num为展开的第几个排列 
	}
	if (vis[num] == 1)
	 return 0;
	vis[num] = 1; 
	return 1; 
}
int bfs()
{
	int front=0,rear=1,i,j,k,c,x,y,xx,yy;
	memcpy(gc[st],qs,sizeof(qs)); //把起始状态放入 
	while (front < rear)
	{
		type temp;
		memcpy(temp,gc[front],sizeof(gc[front])); //获取对头 
		if (memcmp(temp,mb,sizeof(mb))==0)//到达终点
		{
			return front;
		}
		for(k=0; k<9; k++)
		{
			if (temp[k]==0)
				break;
		}
		x = k/3;
		y = k%3; //转2维下标
		for(i=0; i<4; i++)
		{
			xx = dir[i][0] + x;
		    yy = dir[i][1] + y;
		    if (xx>=0&&yy>=0&&xx<3&&yy<3)
		    {
		    	c = 3*xx + yy;
		    	type temp2;
		    	memcpy(temp2,temp,sizeof(temp));
		    	temp2[k] = temp2[c];
				temp2[c] = 0; //进行交换
				if (kangtuo(temp2))//康托展开 ,判重 
				{
					memcpy(gc[rear],temp2,sizeof(temp2));
					step[rear++] = step[front] + 1; 
				}
			}
		 }
		 front++;//进入下一个队列元素
	} 
	return -1;
}
int main()
{
	char ch;
	int i,r;
	init();
	for (i=0; i<9; i++)
	{
		cin>>ch;
		ch == '.' ? qs[i]=0 : qs[i]=ch-'0';
	}
	getchar();
	for (i=0 ;i<9; i++)
	{
		cin>>ch;
		ch == '.' ? mb[i]=0 : mb[i]=ch-'0';
	}
	r = bfs();
	r == -1 ? cout<<r<<endl : cout<<step[r]<<endl;
	return 0;
}