蓝桥 2×3格子移字母 (bfs)

ゞ浴缸里的玫瑰 2022-06-18 08:16 176阅读 0赞

2×3=6个方格中放入ABCDE五个字母，右下角的那个格空着。如图所示。

![1][]

和空格子相邻的格子中的字母可以移动到空格中，比如，图中的C和E就可以移动，移动后的局面分别是：

A B  
D E C

A B C  
D E

为了表示方便，我们把6个格子中字母配置用一个串表示出来，比如上边的两种局面分别表示为：

AB\*DEC  
ABCD\*E

题目的要求是：请编写程序，由用户输入若干表示局面的串，程序通过计算，输出是否能通过对初始状态经过若干次移动到达该状态。可以实现输出1，否则输出0。初始状态为：ABCDE\*

用户输入的格式是：先是一个整数n，表示接下来有n行状态。程序输出也应该是n行1或0

例如，用户输入：

3  
ABCDE\*  
AB\*DEC  
CAED\*B

则程序应该输出：  
1  
1

2012年蓝桥杯高职决赛的最后一题,比八数码要简单多了,题目要求是否能达到,我多加了一步最少的移动次数,用了一个字符数组来判断重复

#include<iostream>  
    #include<string.h>
    #include<cstdio>
    using namespace std;
    char str[7]="ABCDE*",v[1000][7],s[7];;
    int dir[4][2] = {-1,0,0,-1,0,1,1,0};
    int step[10000]={0},st=0;
    int bfs()
    {
    	int front=0,rear=1,i,j,x,y,xx,yy,k,c;
    	char stemp[7],stemp2[7];
    	strcpy(v[0],s);
    	st++;//总共的状态 
    	while (front < rear)
    	{
    		strcpy(stemp,v[front]);//每次获取对头 
    		if (0 == strcmp(stemp,str))//相同 
    		{
    			return front;
    		}
    		for (k=0; k<6; k++) //找出空格下标k
    		  if (stemp[k] == '*')
    		   break;
    		x = k/3; //转成2维下标xy 
    		y = k%3;
    		for (i=0 ;i<4; i++)
    		{
    			xx = dir[i][0] + x; //选择空格位置上下左右 
    			yy = dir[i][1] + y;
    			if (xx<0||yy<0||xx>=2||yy>=3)
    			{
    				continue;
    			}
    			strcpy(stemp2,stemp);
    			c = xx*3+yy;//生成新的空格位置 
    			stemp2[k] = stemp[c];//替换掉 之前的空格 
    			stemp2[c] = '*'; //新的空格位置
    			for (j=0; j<st; j++)
    			{
    				if (strcmp(v[j],stemp2)==0)//判断是否重复 
    				 break;
    			}
    			if (j == st)//状态中没有重复的
    			{
    				strcpy(v[st++],stemp2);//新的状态进入队列 
    				step[rear++] = step[front]+1;
    			}
    		}
    		front++;//对头
    	}
    	return -1;
    }
    int main()
    {
    	int i,j,n;
    	cin>>n;
    	getchar();
    	while (n--)
    	{
    		memset(step,0,sizeof(step));
    		memset(v,0,sizeof(v));
    		st=0;
    		gets(s);
    		cout<<step[bfs()]<<endl;
    	}
    	return 0;
    }

[1]: http://www.lanqiaotiku.com/wp-content/uploads/2013/06/11.jpg