http://acm.pku.edu.cn/JudgeOnline/problem?id=1166
Код:
#include <stdio.h>
const int NMAX = 12;
int a[NMAX];
char b[NMAX][NMAX] = {{0},{"ABDE"},{"ABC"},{"BCEF"},{"ADG"},{"BDEFH"}
,{"CFI"},{"DEGH"},{"GHI"},{"EFHI"}};
int len[NMAX] = {{0},{4},{3},{4},{3},{5},{3},{4},{3},{4}};
int check[NMAX];
int print[NMAX*NMAX];
int Last[NMAX*NMAX];
int pcnt;
int t;
int temp[NMAX*4];
int tcnt;
int min = NMAX*NMAX-1;
int _ok()
{
int i,j;
int c[NMAX];
for(i=0;i<NMAX;i++)
c[i] = a[i];
for(i=0;i<pcnt;i++)
temp[i] = print[i];
tcnt = pcnt;
for(i=4;i<=9;i++)
{
if(c[b[i][0]-'A'+1] != 0)
{
t = 4-c[b[i][0]-'A'+1];
for(j=0;j<t;j++)
temp[tcnt++] = i;
for(j=0;j<len[i];j++)
{
c[b[i][j]-'A'+1]+=t;
if(c[b[i][j]-'A'+1] >= 4)
c[b[i][j]-'A'+1] -= 4;
}
}
}
for(i=1;i<=9;i++)
{
if(c[i] != 0)
return 0;
}
return 1;
}
void recur(int now)
{
int i,j;
if(now > 3)
{
t = _ok();
if(t == 1 && min > tcnt)
{
min = tcnt;
for(i=0;i<tcnt;i++)
Last[i] = temp[i];
}
return;
}
for(i=0;i<4;i++)
{
check[now] = i;
for(j=0;j<i;j++)
print[pcnt++] = now;
for(j=0;j<len[now];j++)
{
a[b[now][j]-'A'+1]+=i;
if(a[b[now][j]-'A'+1] >= 4)
a[b[now][j]-'A'+1] -= 4;
}
recur(now+1);
for(j=0;j<i;j++)
print[--pcnt] = now;
for(j=0;j<len[now];j++)
{
a[b[now][j]-'A'+1] -= i;
if(a[b[now][j]-'A'+1] < 0)
a[b[now][j]-'A'+1] += 4;
}
}
}
void inlet()
{
FILE *op=stdin;
int i;
for(i=1;i<10;i++)
fscanf(op,"%d",&a[i]);
}
void work()
{
int i,j;
for(i=0;i<4;i++)
{
check[1] = i;
for(j=0;j<i;j++)
print[pcnt++] = 1;
for(j=0;j<len[1];j++)
{
a[b[1][j]-'A'+1]+=i;
if(a[b[1][j]-'A'+1] >= 4)
a[b[1][j]-'A'+1] -= 4;
}
recur(2);
for(j=0;j<i;j++)
print[--pcnt] = 0;
for(j=0;j<len[1];j++)
{
a[b[1][j]-'A'+1] -= i;
if(a[b[1][j]-'A'+1] < 0)
a[b[1][j]-'A'+1] += 4;
}
}
}
void outlet()
{
FILE *out=stdout;
int i;
for(i=0;i<min;i++)
{
fprintf(out,"%d ",Last[i]);
}
}
void main()
{
inlet();
work();
outlet();
}