比赛 20120914 评测结果 AATATATA
题目名称 著名医生的药方 最终得分 62
用户昵称 Truth.Cirno 运行时间 3.335 s
代码语言 C++ 内存使用 1.53 MiB
提交时间 2012-09-14 21:48:18
显示代码纯文本
#include <cstdio>
#include <cstring>
using namespace std;

struct record
{
	int data[510];
	bool una[510];
};

int n,p,waynum[510],way[510][510],outnum/*,outp[60000][510]*/;
bool map[510][510];

void swap(int& x,int& y)
{
	int temp;
	temp=x;
	x=y;
	y=temp;
}

record change(record now,int deep,int pos)
{
	int i,bef;
	bef=now.data[deep-1];
	now.data[deep]=pos;
	now.una[pos]=true;
	if (bef)
		for (i=0;i<waynum[bef];i++)
			now.una[way[bef][i]]=true;
	return(now);
}

void dfs(record now,int deep)
{
	int i;
	if (deep>p)
	{
//		for (i=1;i<=p;i++)
//			outp[outnum][i]=now.data[i];
		outnum++;
		return;
	}
	int temp,bef;
	temp=now.data[deep];
	bef=now.data[deep-1];
	if (temp)
	{
		if (now.una[temp])
			return;
		else
		{
			if (bef)
				for (i=0;i<waynum[bef];i++)
					now.una[way[bef][i]]=true;
			dfs(now,deep+1);
			return;
		}
	}
	int aft;
	aft=now.data[deep+1];
	for (i=0;i<waynum[bef];i++)
	{
		if (!now.una[way[bef][i]]&&map[way[bef][i]][aft])
		{
			dfs(change(now,deep,way[bef][i]),deep+1);
		}
	}
}

void dfs2(record now,int deep)
{
	int i;
	if (deep>p)
	{
		for (i=1;i<p;i++)
			printf("%d ",now.data[i]);
		printf("%d\n",now.data[p]);
//		outnum++;
		return;
	}
	int temp,bef;
	temp=now.data[deep];
	bef=now.data[deep-1];
	if (temp)
	{
		if (now.una[temp])
			return;
		else
		{
			if (bef)
				for (i=0;i<waynum[bef];i++)
					now.una[way[bef][i]]=true;
			dfs2(now,deep+1);
			return;
		}
	}
	int aft;
	aft=now.data[deep+1];
	for (i=0;i<waynum[bef];i++)
	{
		if (!now.una[way[bef][i]]&&map[way[bef][i]][aft])
		{
			dfs2(change(now,deep,way[bef][i]),deep+1);
		}
	}
}

int main(void)
{
	freopen("doctor.in","r",stdin);
	freopen("doctor.out","w",stdout);
	char str[2000];
	int iex,i,j,k,len,num;
	record rec={0};
	scanf("%d\n",&n);
	for (i=0;i<n;i++)
	{
		way[0][i]=i+1;
		map[0][i+1]=true;
		map[i+1][0]=true;
	}
	waynum[0]=n;
	for (iex=1;iex<=n;iex++)
	{
		scanf("%[^\n]\n",&str);
		while (str[0]<'0'||str[0]>'9')
			scanf("%[^\n]\n",&str);
		len=strlen(str);
		for (i=0;i<len;i++)
		{
			if (str[i]>='0'&&str[i]<='9')
			{
				j=i;
				while (str[j]>='0'&&str[j]<='9')
					j++;
				j--;
				num=0;
				for (k=i;k<=j;k++)
					num=num*10+str[k]-'0';
				way[iex][waynum[iex]++]=num;
				map[iex][num]=true;
				i=j;
			}
		}
		for (i=0;i<=waynum[iex]-2;i++)
			for (j=0;j<=waynum[iex]-i-2;j++)
				if (way[iex][j]>way[iex][j+1])
					swap(way[iex][j],way[iex][j+1]);
	}
	scanf("%d",&p);
	for (i=1;i<=p;i++)
		scanf("%d",&rec.data[i]);
	dfs(rec,1);
	printf("%d\n",outnum);
//	for (i=0;i<outnum;i++)
//	{
//		for (j=1;j<p;j++)
//			printf("%d ",outp[i][j]);
//		printf("%d\n",outp[i][p]);
//	}
	dfs2(rec,1);
	return(0);
}