2415.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include"iostream.h"
#include"queue"
#include"algorithm"

using namespace std;

char edge[51][51];
int sign[51][51][51],n,p1,p2,p3;
struct node
{
	int p[3];
	int steps;
};
queue<node> q;

bool init()
{
	int i,j,k;
	cin>>n>>p1>>p2>>p3;
	if(n==0)return 0;
	
	for(i=0;i<n;i++)
	for(j=0;j<n;j++)
		cin>>edge[i][j];

	for(i=0;i<n;i++)
	for(j=0;j<n;j++)
	for(k=0;k<n;k++)
		sign[i][j][k]=0;
	
	while(!q.empty())
		q.pop();

	return 1;
}
inline void set(int a,int b,int c,int v)
{
	sign[a][b][c]=sign[a][c][b]=sign[b][a][c]=sign[b][c][a]=sign[c][a][b]=sign[c][b][a]=v;
}

int doit()
{
	int i,j;
	node nd,ndt;
	
	nd.p[0]=p1-1;	nd.p[1]=p2-1;	nd.p[2]=p3-1;
	nd.steps=1;

	set(nd.p[0],nd.p[1],nd.p[2],1);
	q.push(nd);
	
	while(!q.empty())
	{
		nd=q.front();q.pop();
		if(nd.p[0]==nd.p[1]&&nd.p[1]==nd.p[2])
			return sign[nd.p[0]][nd.p[1]][nd.p[2]];
		
		for(i=0;i<n;i++)
		{
			for(j=0;j<3;j++)
			if(!sign[i][nd.p[(j+1)%3]][nd.p[(j+2)%3]]&&
				edge[nd.p[j]][i]==edge[nd.p[(j+1)%3]][nd.p[(j+2)%3]])
			{
				set(i,nd.p[(j+1)%3],nd.p[(j+2)%3],nd.steps+1);
				ndt=nd;
				ndt.steps++;
				ndt.p[j]=i;
				q.push(ndt);
			}
		}
	}
	return 0;
}

int main()
{
	int ans;
	while(init())
	{
		ans=doit();
		if(!ans)cout<<"impossible"<<endl;
		else cout<<ans-1<<endl;
	}
	return 0;
}