历届试题九宫重排 (bfs 八数码问题)

柔光的暖阳◎ 2022-07-04 21:28 200阅读 0赞

问题描述

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

输入格式

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

输出格式

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

样例输入

12345678.  
123.46758

样例输出

样例输入

13524678.  
46758123.

样例输出

这题困扰我很久 网站找了些八数码的代码看看,什么哈希太深奥了,看不懂阿,后来找到了一段比较好理解的

代码:

#include "iostream"
    #include "algorithm"
    #include "vector"
    #include "set"
    #include "string.h"
    #include "ctype.h"
    #define M 1000000
    using namespace std;
    
    typedef int type[9];
    type qs[M];
    type mb;
    int front,rear;
    int dir[4][2]={-1,0,0,-1,0,1,1,0};
    int dis[M]={0}; 
    set<int> vis; //容器，存储不同的值 
    int panchong(int x)
    {
    	int i,sum=0;
    	for (i=0; i<9; i++)
    	{
    		sum = sum*10+qs[x][i];
    	}
    	if (vis.count(sum)) //容器中有相同 
    	{
    		return 0;
    	}
    	vis.insert(sum);//插入容器 
    	return 1;
    }
    int bfs()
    {
    	front = 1;
    	rear = 2;
    	int i,j,k=0,c,x,y,xx,yy;
    	while (front < rear)
    	{
    		type &s = qs[front]; //s指向qs[front] 
    		if (memcmp(s,mb,sizeof(mb)) == 0)
    		{
    			return front;
    		}
    		for (k=0; k<9; k++)
    		{
    			if (s[k]==0)
    			 break;
    		}
    		x = k/3;
    		y = k%3; // 转成二维数组
    		for (i=0; i<4; i++)
    		{
    			xx = x+dir[i][0];
    			yy = y+dir[i][1];
    			if(xx>=0 && xx<3 && yy>=0 && yy<3)
    			{
    				type &t = qs[rear];//t指向qs[rear] 
    				memcpy(t,s,sizeof(s));
    				t[k] = s[xx*3+yy]; //交换空格与数字位置 
    				t[xx*3+yy] = s[k];
    				if (panchong(rear))//得到新的图进行判断重复 
    				{
    					dis[rear] = dis[front]+1;
    					rear++;
    				}
    			}
    		}
    		front++;
    	}
    	return -1; 
    }
    int main()
    {
    	int i,j,cnt;
    	char ch[10],ch2[10];
    	scanf("%s%s",ch,ch2); 
    	for (i=0; i<9; i++)
    	{
    		ch[i]<='8'&&ch[i]>='0' ? qs[1][i]=ch[i]-'0' : qs[1][i]=0; 
    	}
    	for (i=0; i<9; i++)
    	{ 
    		ch2[i]<='8'&&ch2[i]>='0' ? mb[i]=ch2[i]-'0' : mb[i]=0;
    	} 
    	cnt = bfs();
    	if(cnt>0)
    	{
    		cout<<dis[cnt]<<endl;
    	 } 
    	 else
    	 {
    	 	cout<<-1<<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