3038807_ac_578ms_8776k.cpp

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

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

using namespace std;

char str[1<<20+1];
int d, n;
int len[21];
int pos[21];
int st, ed, mid;
int mark[1<<20+1], lenth[1<<20+1];
int base[21];

int calc(int tmp[])
{
	int i, ret = 0;

	for(i = 1; i <= d; i++)
	{
		ret += base[i]*tmp[i];
	}
	return ret;
}

int bfs(int a,int b)
{
	int i, s, t, tt, tmp[21];
	queue <int> que;

	que.push(a);
	memset(mark,0,sizeof(mark));
	mark[a] = 1;
	lenth[a] = 0;
	while(!que.empty())
	{
		s = t = que.front();
		que.pop();
		for(i = 1; i <= d; i++)
		{
			tmp[i] = t/base[i];
			t %= base[i];
		}
		t = s;
		for(i = 1; i <= d; i++)
		{
			tmp[i]-=1;
			if(tmp[i]>=0)
			{
				tt = calc(tmp);
				if(!mark[tt]&&str[tt]!='#')
				{
					mark[tt] = 1;
					lenth[tt] = lenth[t]+1;
					if(tt==b)
					{
						return lenth[tt];
					}
					que.push(tt);
				}
			}
			tmp[i]+=2;
			if(tmp[i]<len[i])
			{
				tt = calc(tmp);
				if(!mark[tt]&&str[tt]!='#')
				{
					mark[tt] = 1;
					lenth[tt] = lenth[t]+1;
					if(tt==b)
					{
						return lenth[tt];
					}
					que.push(tt);
				}
			}
			tmp[i]--;
		}
	}
	return -1;
}

int main()
{
	int i, l, t, ans;

	while(scanf("%d",&d)==1,d)
	{
		l = 1;
		for(i = d; i > 0; i--)
		{
			scanf("%d",&len[i]);
			if(i!=d)
			{
				l *= len[i];
			}
		}
		base[d] = 1;
		for(i = d-1; i > 0; i--)
		{
			base[i] = base[i+1]*len[i+1];
		}
		for(i = 0; i < l; i++)
		{
			scanf("%s",&str[i*len[d]]);
		}
		for(i = 0; i < l*len[d]; i++)
		{
			if(str[i]=='T')
			{
				st = i;
			}
			if(str[i]=='M')
			{
				ed = i;
			}
			if(str[i]=='S')
			{
				mid = i;
			}
		}
		str[ed] = '#';
		t = bfs(st,mid);
		if(t==-1)
		{
			puts("No solution. Poor Theseus!");
			continue;
		}
		ans = t;
		str[ed] = 'M';
		t = bfs(mid,ed);
		if(t==-1)
		{
			puts("No solution. Poor Theseus!");
			continue;
		}
		ans += t;
		t = bfs(ed,st);
		if(t==-1)
		{
			puts("No solution. Poor Theseus!");
			continue;
		}
		ans += t;
		printf("Theseus needs %d steps.\n",ans);
	}
	return 0;
}