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(); }