1560.txt

杭电acm解题报告2001---2099.

#include<cstdio>
#include<string>
#include<queue>
#define MAX 1000001
using namespace std;
char str[10][10];
int n,d[8]={1},g[MAX];
bool f[MAX];
struct Node
{
    char ps[8];
    int deep;
}st;
queue<Node> SQ;

int hash(Node p)
{
    int i,s=0,t;
    for(i=0;i<n;i++)
        s+=d[i]*p.ps[i];
    t=s%MAX;
    while(f[t]!=0 && g[t]!=s)
        t=(t+1)%MAX;
    if(f[t])
        return -1;
    f[t]=true;
    return g[t]=s;
}

int bfs()
{
    Node pt,now;
    bool flag=false,bv[30];
    char pch;
    int i,j;
    
    while(!SQ.empty())
    {
        now=SQ.front();
        SQ.pop();
        
        flag=false;
        for(i=0;i<30;i++)    bv[i]=false;
        for(i=0;i<n;i++)
        {
            pch=str[i][ now.ps[i] ];
            if(pch==0)    continue;
            if(!bv[ pch-'A' ])
            {
                bv[ pch-'A' ]=true;
                flag=true;
                pt=now;
                for(j=i;j<n;j++)
                    if(pch== str[j][ pt.ps[j] ])
                    {
                        pt.ps[j]++;
                    }
                pt.deep++;
                if(hash(pt)!=-1)
                    SQ.push(pt);
            }
        }//for
        if(!flag)
            return now.deep;
    }
}
int main()
{
    int i,t;

    for(i=1;i<8;i++)
        d[i]=d[i-1]*6;
    scanf("%d",&t);
    while(t--)
    {
        memset(f,0,sizeof(f));
        scanf("%d",&n);
        for(i=0;i<n;i++)
            scanf("%s",str[i]);
        while(!SQ.empty())
            SQ.pop();
        SQ.push(st);
        hash(st);
        printf("%d\n",bfs());
    }
}