zoj 1757 Bright Bracelet

zoj 1757 Bright Bracelet

#include <iostream>#include <cstdlib>#include <cmath>#include <stdio.h>#include <string.h>#include <algorithm>using namespace std;const int inf=1<<28;int b[8];char input[12][10];int brac[12][10];int ans[15];int mark[15];int state[4500][8][8];   int mi[12];int n;int Min;int ones (int key){ int c=0; while (key) {  key&=(key-1);  c++; } return c;}int main(){ mi[0]=1; for (int i=1;i<=11;++i)  mi[i]=mi[i-1]<<1;    while (scanf("%d",&n) ,n)    {          for (int i=0;i<8;i++)   scanf("%d",&b[i]);          for (int i=0;i<n;i++)    {       scanf("%s",input[i]);      for (int j=0;j<8;j++)       brac[i][j]=input[i][j]-'A';    }    memset(state,-1,sizeof(state));    for (int i=0;i<8;i++)    {     int l=brac[0][(i+4)%8],r=brac[0][i];     state[mi[0]][l][r]=0;    }          int tot=mi[n]-1;      for (int i=1;i<n;i++)     for (int x=1;x<=tot;x++)          if (ones(x)==i)        {       for (int q=0;q<8;q++)        for (int p=0;p<8;p++)if (state[x][q][p]!=-1){for (int s=0;s<n;s++)      if ((mi[s]&x)==0)        {        for (int k=0;k<8;k++)          {int l=brac[s][(k+4)%8];int r=brac[s][k];if (p==l)  { if (i==n-1 && q!=r) continue; if (state[mi[s]+x][q][r]==-1 || state[x][q][p]+b[p]<state[mi[s]+x][q][r])  state[mi[s]+x][q][r]=state[x][q][p]+b[p];}if (q==r)  { if (i==n-1 && l!=p) continue; if (state[mi[s]+x][l][p]==-1 || state[x][q][p]+b[q]<state[mi[s]+x][l][p])  state[mi[s]+x][l][p]=state[x][q][p]+b[q];}          }}         }      }    int Min=inf;    for (int i=0;i<8;i++)      if (state[tot][i][i]!=-1 )         Min=min(Min,state[tot][i][i]+b[i]);if (Min==inf)          printf("impossiblen");          else printf("%dn",Min);    }    return 0;}