网格中移动字母

网格中移动字母

时间： 1ms        内存：128M

描述：

    2x3=6个方格中放入ABCDE五个字母，右下角的那个格空着。

    和空格子相邻的格子中的字母可以移动到空格中，比如，图中的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
0

提示：

参考答案（内存最优[1104]）：

#include<stdio.h>
#include<string.h>

char a[10];
char b[750][7];
char c[6]={'A','B','C','D','E','*'};
int t[4][2]={1,0,0,1,0,-1,-1,0};
int temp;

int fun()
{
    int i,j,x,y,q,front=0,rear,newx,newy,newz,z;
    char v[10],u[10];
    memset(b,0,sizeof(b));
    strcpy(b[front],a);
    rear=1;
    while(front<rear)
    {
        strcpy(u,b[front]);
        if(!(strcmp(u,c))) return 1;
        else
        {
            for(z=0;z<6;z++)
                if(u[z]=='*') break;
                x=z/3;
                y=z%3;
            for(i=0;i<4;i++)
            {
                newx=x+t[i][0];
                newy=y+t[i][1];
                newz=newx*3+newy;
                strcpy(v,u);
                if(newx>=0&&newx<2&&newy>=0&&newy<3)
                {
                    v[z]=u[newz];
                    v[newz]=u[z];
                    q=1;
                    for(j=0;j<rear;j++)
                        if(!strcmp(v,b[j])){ q=0; break;}
                    if(q)
                            strcpy(b[++rear],v);

                }
            }
        }
            front++;
    }
        return 0;
}

int main()
{
    int k;
    scanf("%d",&k);
    while(k--)
    {
        temp=1;
        scanf("%s",a);
        printf("%d\n",fun());
    }
    return 0;
}

参考答案（时间最优[0]）：

#include <iostream>
#include <cstring>
#define MAX 1000
using namespace std;
char str[MAX+1][7];//     ABCDE* 123450  6进制   
char count[MAX+1];    //存储其中*的位置
int getNum(char str[])  
{
	int sum=0;
	for(int i=0;i<6;i++)
	{
		sum*=6;
		if(str[i]=='*')	continue;
		sum+=str[i]-'A'+1;
	}
	return sum;
}
int main()
{	
	int exchange[6][3]={{1,3,-1},{0,2,4},{1,5,-1},{0,4,-1},{1,3,5},{2,4,-1}};
	char aim[7]="ABCDE*";
	int n;
	cin>>n;
	while(n--)
	{
		bool haveUsed[6*6*6*6*6*6]={0};
		int kstr=0;
		int present=0;
		int i;
		for(i=0;i<6;i++)
		{
			cin>>str[0][i];
			if(str[0][i]=='*')count[0]=i;
		}
		str[kstr++][6]='\0';
		bool achive=true;
		int tip=getNum(str[0]);
		haveUsed[tip]=true;
		while(strcmp(str[present++],aim))
		{
			if(kstr>=MAX-1)
			{	
				achive=false;
				break;
			}
			int starLocal=count[present-1];
			for(i=0;i<3;i++)
			{
				int willBe=exchange[starLocal][i];
				if(willBe>=0)
				{	
					strcpy(str[kstr],str[present-1]);
					str[kstr][starLocal]=str[kstr][willBe];
					str[kstr][willBe]='*';
					count[kstr]=willBe;
					tip=getNum(str[kstr]);
					if(!haveUsed[tip])
					{
						haveUsed[tip]=true;
						kstr++;
					}
				}
			}
			if(present==kstr)
			{
				achive=false;
				break;
			}
		}
		if(achive)cout<<1<<endl;
		else cout<<0<<endl;
	}
	return 0;
}

题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。