2803171_tle.cpp

来自「北大大牛代码 1240道题的原代码 超级权威」· C++ 代码 · 共 140 行

#include <stdio.h>
#include <queue>

using namespace std;

char a[7], b[7];
int st, ed;
struct node
{
	char num[7];
	int pos;
	int step;
};
int mark[1000000][6];

queue <node> que;

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

	strcpy(t.num,a);
	st = atoi(a);
	ed = atoi(b);
	memset(mark,0,sizeof(mark));
	mark[st][0] = 1;
	t.step = 0;
	t.pos = 0;
	que.push(t);
	while(!que.empty())
	{
		t = que.front();
		que.pop();
		if(t.pos!=0)//swap0
		{
			p = t;
			ch = p.num[p.pos];
			p.num[p.pos] = p.num[0];
			p.num[0] = ch;
			p.step++;
			tmp = atoi(p.num);
			if(tmp==ed)
			{
				printf("%d\n",p.step);
				return ;
			}
			if(!mark[tmp][p.pos])
			{
				mark[tmp][p.pos] = 1;
				que.push(p);
			}
		}
		if(t.pos!=5)//swap1
		{
			p = t;
			ch = p.num[p.pos];
			p.num[p.pos] = p.num[5];
			p.num[5] = ch;
			p.step++;
			tmp = atoi(p.num);
			if(tmp==ed)
			{
				printf("%d\n",p.step);
				return ;
			}
			if(!mark[tmp][p.pos])
			{
				mark[tmp][p.pos] = 1;
				que.push(p);
			}
		}
		if(t.pos!=0)//left
		{
			p = t;
			p.pos--;
			p.step++;
			tmp = atoi(p.num);
			if(!mark[tmp][p.pos])
			{
				mark[tmp][p.pos] = 1;
				que.push(p);
			}
		}
		if(t.pos!=5)//right
		{
			p = t;
			p.pos++;
			p.step++;
			tmp = atoi(p.num);
			if(!mark[tmp][p.pos])
			{
				mark[tmp][p.pos] = 1;
				que.push(p);
			}
		}
		if(t.num[t.pos]!='9')//up
		{
			p = t;
			p.num[t.pos]++;
			p.step++;
			tmp = atoi(p.num);
			if(tmp==ed)
			{
				printf("%d\n",p.step);
				return ;
			}
			if(!mark[tmp][p.pos])
			{
				mark[tmp][p.pos] = 1;
				que.push(p);
			}
		}
		if(t.num[t.pos]!='0')//up
		{
			p = t;
			p.num[t.pos]--;
			p.step++;
			tmp = atoi(p.num);
			if(tmp==ed)
			{
				printf("%d\n",p.step);
				return ;
			}
			if(!mark[tmp][p.pos])
			{
				mark[tmp][p.pos] = 1;
				que.push(p);
			}
		}
	}
}

int main()
{	
	scanf("%s%s",a,b);
	bfs();
	return 0;
}