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

迈不过友情╰ 2022-06-18 08:20 206阅读 0赞

问题描述

如下面第一个图的九宫格中，放着 1~8 的数字卡片，还有一个格子空着。与空格子相邻的格子中的卡片可以移动到空格中。经过若干次移动，可以形成第二个图所示的局面。  
![RequireFile.do_fid_qYebaGed][] ![RequireFile.do_fid_HQ3JFM72][]  
　　我们把第一个图的局面记为：12345678.  
　　把第二个图的局面记为：123.46758  
　　显然是按从上到下，从左到右的顺序记录数字，空格记为句点。  
　　本题目的任务是已知九宫的初态和终态，求最少经过多少步的移动可以到达。如果无论多少步都无法到达，则输出-1。

输入格式

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

输出格式

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

样例输入

12345678.  
123.46758

样例输出

样例输入

13524678.  
46758123.

样例输出

这道题在寒假的时候就想做了,但那时候啥都不会,现在终于自己写出来,算是把寒假时候的愿望实现了.上午写的[2\*3格子移字母][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;
    }

[RequireFile.do_fid_qYebaGed]: http://lx.lanqiao.cn/RequireFile.do?fid=qYebaGed
[RequireFile.do_fid_HQ3JFM72]: http://lx.lanqiao.cn/RequireFile.do?fid=HQ3JFM72
[2_3]: http://blog.csdn.net/qq_36238595/article/details/68944498