蓝桥卡片换位（bfs）

偏执的太偏执、 2022-06-18 08:26 161阅读 0赞

你玩过华容道的游戏吗？  
这是个类似的，但更简单的游戏。  
看下面 3 x 2 的格子

\+---+---+---+  
| A | \* | \* |  
\+---+---+---+  
| B |   | \* |  
\+---+---+---+

在其中放5张牌，其中A代表关羽，B代表张飞，\* 代表士兵。  
还有一个格子是空着的。

你可以把一张牌移动到相邻的空格中去(对角不算相邻)。  
游戏的目标是：关羽和张飞交换位置，其它的牌随便在哪里都可以。

输入格式：  
输入两行6个字符表示当前的局面

输出格式：  
一个整数，表示最少多少步，才能把AB换位（其它牌位置随意）

例如，输入：  
\* A  
\*\*B

程序应该输出：  
17

再例如，输入：  
A B  
\*\*\*

程序应该输出：  
12

思路： 与八数码差不多的思路，移动空格

#include<iostream>  
    #include<string.h>
    #include<algorithm>
    #include<cstdio>
    #define M 1000000
    using namespace std;
    int qs[6],mb[6],gc[M][6],A,B,v[M]={0};
    int step[M]={0};
    int dir[4][2] = {-1,0,0,-1,0,1,1,0};
    int cz(int *a)
    {
    	int x,y,i,xx,yy;
    	for (i=0; i<6; i++)
    	{
    		if (a[i]==1)
    		{
    			x = i;
    		}
    		if (a[i]==2)
    		{
    			y = i;
    		}
    	}
    	if (x==B&&y==A)//现在的A在之前b上，现在的b在之前的A上
    	 return 1;
    	return 0; 
    }
    int bfs()
    {
    	int i,j,c,front=0,rear=1,x,y,xx,yy,k,temp[6];
    	memcpy(gc[0],qs,sizeof(qs));
    	while (front < rear)
    	{
    		memcpy(qs,gc[front],sizeof(gc[front]));
    		if (cz(qs))
    		{
    			return front;
    		}
    		for (k=0; k<6; k++)
    		{
    			if (qs[k] == 0)
    			{
    				break;
    			}
    		}
    		x = k/3;
    		y = k%3;
    		for (i=0; i<4; i++)
    		{
    			xx = dir[i][0] + x;
    			yy = dir[i][1] + y;
    			if (xx>=0&&xx<2&&yy>=0&&yy<3)
    			{
    				c = xx*3+yy;
    				memcpy(temp,qs,sizeof(qs));
    				temp[k] = qs[c];
    				temp[c] = 0;
    				for (j=0; j<rear; j++)
    				{
    					if (memcmp(temp,gc[j],sizeof(gc[j])) == 0)
    					{
    						break;
    					}
    				}
    				if (j==rear)//无重复，放入 
    				{
    					step[rear] = step[front]+1;
    					memcpy(gc[rear++],temp,sizeof(temp));
    				}
    			}
    		}
    		front++;
    	}
    }
    int main()
    {
    	int i,j,k=0,r;
    	char ch[5];
    	for (i=0; i<2; i++)
    	{
    		gets(ch);
    		for (j=0; ch[j]; j++)
    		{
    			if (ch[j]=='A')
    			{
    				qs[k++] = 1;
    				A = 3*i+j;
    			}
    			else if (ch[j]=='B')
    			{
    				qs[k++] = 2;
    				B = 3*i+j;
    			}
    			else if (ch[j]=='*')
    			{
    				qs[k++] = 3;
    			}
    			else
    			{
    				qs[k++] = 0;
    			}
    		}
    	}
    	cout<<step[bfs()];
    	return 0;
    }