2803422_mle.cpp

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

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

int st, ed;
int max;
struct node
{
	int num;
	int pos;
	int mov;
	int step;
};
int mark[1000000][6];

node que[7000000];
int f, r;

int num[] = {100000,10000,1000,100,10,1};

void bfs()
{
	int tmp, tt;
	node t, p;

	f = r = -1;
	t.num = st;
	memset(mark,0,sizeof(mark));
	mark[st][0] = 1;
	t.step = 0;
	t.pos = 0;
	t.mov = 0;
	que[++r] = t;
	while(f!=r)
	{
		f++;
		t = que[f];
				tmp = t.num;
		tmp /= num[t.pos];
		//tmp %= 10;
		tmp = tmp - tmp/10*10;
		tt = tmp;
		if(tt!=9)//up
		{
			p = t;
			p.num += num[p.pos];
			p.step++;
			tmp = p.num;
			if(tmp==ed)
			{
				printf("%d\n",p.step);
				return ;
			}
			if(p.step<=max&&!mark[tmp][p.pos])
			{
				mark[tmp][p.pos] = 1;
				que[++r] = p;
			}
		}
		if(tt!=0)//down
		{
			p = t;
			p.num -= num[p.pos];
			p.step++;
			tmp = p.num;
			if(tmp==ed)
			{
				printf("%d\n",p.step);
				return ;
			}
			if(p.step<=max&&!mark[tmp][p.pos])
			{
				mark[tmp][p.pos] = 1;
				que[++r] = p;
			}
		}
		if(t.pos!=0)//swap0
		{
			p = t;
			tt = p.num/num[0];
			tmp = p.num;
			tmp /= num[p.pos];
			//tmp %= 10;
			tmp = tmp - tmp/10*10;
			//p.num %= num[0];
			p.num = p.num - p.num/num[0]*num[0];
			p.num -= tmp*num[p.pos];
			p.num += tmp*num[0];
			p.num += tt*num[p.pos];
			p.step++;
			tmp = p.num;
			if(tmp==ed)
			{
				printf("%d\n",p.step);
				return ;
			}
			if(p.step<=max&&!mark[tmp][p.pos])
			{
				mark[tmp][p.pos] = 1;
				que[++r] = p;
			}
		}
		if(t.pos!=5)//swap1
		{
			p = t;
			//tt = p.num%10;
			tt = p.num - p.num/10*10;
			tmp = p.num;
			tmp /= num[p.pos];
			//tmp %= 10;
			tmp = tmp - tmp/10*10;
			p.num -= tmp*num[p.pos];
			p.num -= tt;
			p.num += tmp;
			p.num += tt*num[p.pos];
			tmp = p.num;
			p.step++;
			if(tmp==ed)
			{
				printf("%d\n",p.step);
				return ;
			}
			if(p.step<=max&&!mark[tmp][p.pos])
			{
				mark[tmp][p.pos] = 1;
				que[++r] = p;
			}
		}
		if(t.mov>=5)
			continue;
		if(t.pos!=0)//left
		{
			p = t;
			p.pos--;
			p.step++;p.mov++;
			tmp = p.num;
			if(p.mov<=5&&p.step<=max&&!mark[tmp][p.pos])
			{
				mark[tmp][p.pos] = 1;
				que[++r] = p;
			}
		}
		if(t.pos!=5)//right
		{
			p = t;
			p.pos++;
			p.step++;p.mov++;
			tmp = p.num;
			if(p.mov<=5&&p.step<=max&&!mark[tmp][p.pos])
			{
				mark[tmp][p.pos] = 1;
				que[++r] = p;
			}
		}
	}
}

int main()
{	
	int i;
	char a[7], b[7];

	max = 5;
	scanf("%s%s",a,b);
	st = atoi(a);
	ed = atoi(b);
	for(i = 0; i < 6; i++)
		max += abs(a[i]-b[i]);
	bfs();
	//printf("%d\n",r);
	return 0;
}