比赛 |
20120919dfs |
评测结果 |
AAAAATTTAA |
题目名称 |
虫食算 |
最终得分 |
70 |
用户昵称 |
苏轼 |
运行时间 |
3.207 s |
代码语言 |
C++ |
内存使用 |
3.13 MiB |
提交时间 |
2012-09-19 20:56:46 |
显示代码纯文本
#include<iostream>
#include<stdio.h>
using namespace std;
int number,a[27],b[27],c[27],r[27],answer=0,biao,j[27],used[27];
int p,p1,p2;
char q[27],w[27],e[27];
void first();
void dfs(int x);
void out();
int check(int x);
int main()
{
freopen ("alpha.in","r",stdin);
freopen ("alpha.out","w",stdout);
first();
dfs(-1);
out();
return 0;
}
void first()
{
cin>>number>>q>>w>>e;
for (int i=0;i<number;i++)
{
a[i]=q[i]-'A';
b[i]=w[i]-'A';
c[i]=e[i]-'A';
r[i]=-1;
j[i]=0;
used[i]=1;
}
j[number]=0;
}
void out()
{
for (int i=0;i<number;i++)
{
cout<<r[i]<<' ';
}
}
void dfs(int x)
{
biao=x;
if (x==number-1)
{
if (check(x))
{
answer++;
}
}
else
{
if (answer!=0)
{
return;
}
else
{
if (!check(x))
{
return;
}
else
{
for (int i=0;i<number;i++)
{
biao=x;
if (!used[i])
{
continue;
}
x++;
r[x]=i;
used[i]=0;
dfs(x);
x--;
used[i]=1;
if (answer!=0)
{
return;
}
}
}
}
}
}
int check(int x)
{
if (x==number-1)
{
for (int i=number-1;i>=0;i--)
{
if ((r[a[i]]+r[b[i]]+j[i+1])%number!=r[c[i]])
{
return false;
}
else
{
j[i]=(r[a[i]]+r[b[i]]+j[i+1])/number;
}
}
}
else
{
for (int i=number-1;i>=0;i--)
{
if (a[i]<=x&&b[i]<=x&&c[i]<=x)
{
p=(r[a[i]]+r[b[i]])%number;
if (p==r[c[i]]||(p+1)%number==r[c[i]])
{
}
else
{
return false;
}
}
}
for (int i=number-1;i>=0;i--)
{
if (a[i]>x&&b[i]<=x&&c[i]<=x)
{
p1=(r[c[i]]-r[b[i]]+number)%number;
if (p1==0)
{
p2=number-1;
}
else
{
p2=(p1-1)%number;
}
if (!used[p1]&&!used[p2])
{
return false;
}
}
}
for (int i=number-1;i>=0;i--)
{
if (a[i]<=x&&b[i]>x&&c[i]<=x)
{
p1=(r[c[i]]-r[a[i]]+number)%number;
if (p1==0)
{
p2=number-1;
}
else
{
p2=(p1-1)%number;
}
if (!used[p1]&&!used[p2])
{
return false;
}
}
}
for (int i=number-1;i>=0;i--)
{
if (a[i]<=x&&b[i]<=x&&c[i]>x)
{
p1=(r[a[i]]+r[b[i]])%number;
p2=(p1+1)%number;
if (!used[p1]&&!used[p2])
{
return false;
}
}
}
}
for (int i=0;i<number;i++)
{
j[i]=0;
}
return (true);
}