比赛 |
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);
}