2150292_ac_0ms_25668k.c

北大大牛代码 1240道题的原代码 超级权威

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

int mark[6543211];
char dia[8];
long queue[3000];
int f, r;

void input()
{
	int i, n;
	long t;

	scanf("%d",&n);
	for(i = 0; i < n; i++)
	{
		scanf("%ld",&t);
		printf("%d\n",mark[t]);
	}
}

void bfs()
{
	int i, a, b;
	long t;
	char ch, tmp[8];
	
	f = r = -1;
	queue[++r] = 123456;
	mark[123456] = 0;
	while(f!=r)
	{
		f++;
		ltoa(queue[f],dia,10);
	//	puts(dia);
	//	system("pause");
		if(queue[f]<1000000)
		{
			strcpy(tmp,"0");
			strcat(tmp,dia);
			strcpy(dia,tmp);
			ch = tmp[0];
			tmp[0] = tmp[2];
			tmp[2] = ch;
			t = atol(tmp);
			if(mark[t]==-1)
			{
				mark[t] = mark[queue[f]]+1;
				queue[++r] = t;
			}
			strcpy(tmp,dia);
			ch = tmp[0];
			tmp[0] = tmp[4];
			tmp[4] = ch;
			t = atol(tmp);
			if(mark[t]==-1)
			{
				mark[t] = mark[queue[f]]+1;
				queue[++r] = t;
			}
			strcpy(tmp,dia);
			ch = tmp[0];
			tmp[0] = tmp[6];
			tmp[6] = ch;
			t = atol(tmp);
			if(mark[t]==-1)
			{
				mark[t] = mark[queue[f]]+1;
				queue[++r] = t;
			}
		}
		else
		{
			strcpy(tmp,dia);
			for(i = 0; dia[i]!='\0'; i++)
				if(dia[i]=='0')
					break;
			a = i+1;b = i-1;
			if(i==1)
				b = 6;
			if(i==6)
				a = 1;
			ch = tmp[i];
	        tmp[i] = tmp[a];
	        tmp[a] = ch;
			t = atol(tmp);
			if(mark[t]==-1)
			{
				mark[t] = mark[queue[f]]+1;
				queue[++r] = t;
			}
			strcpy(tmp,dia);
			ch = tmp[i];
	        tmp[i] = tmp[b];
	        tmp[b] = ch;
			t = atol(tmp);
			if(mark[t]==-1)
			{
				mark[t] = mark[queue[f]]+1;
				queue[++r] = t;
			}
			if(i%2==0)
			{
				strcpy(tmp,dia);
				ch = tmp[i];
				tmp[i] = tmp[0];
				tmp[0] = ch;
				t = atol(tmp);
	    		if(mark[t]==-1)
				{
			    	mark[t] = mark[queue[f]]+1;
			    	queue[++r] = t;
				}
			}
		}
	}
}

void init()
{
	memset(mark,-1,sizeof(mark));
	bfs();
}

int main()
{
	init();
 	input();
	return 1;
}