这道题目算法就不说了。。关键是我这个实现方法还是很有意思的。。
我直接用一个类来表示状态。。大大简化了代码(*^__^*) 。。
const int maxn=20;
typedef unsigned long long ull;
int n,m;
struct State
{
    ull s;
    State(ull _s=0):s(_s){}
    int get(int i){return s>>(3*i)&7;}
    int operator[](int i){return get(i);}
    void set(int i,int x){s&=~(7ULL<<(3*i));s|=ull(x)<<(3*i);}
    bool operator<(const State&o)const
    {return s<o.s;}
    void normal()
    {
        static int tmp[10],cnt;
        memset(tmp,0,sizeof(tmp));
        cnt=0;
        for(int i=0;i<=m;i++)
        {
            int t=get(i);
            if(!t)continue;
            if(!tmp[t]) tmp[t]=++cnt;
            set(i,tmp[t]);
        }
    }
    void Merge(int a,int b)
    {
        for(int i=0;i<=m;i++)
            if(get(i)==b)
                set(i,a);
        normal();
    }
    bool LegalAsEnd()const
    {
        return s==0;
    }
    void NextRow()
    {
        s<<=3;
    }
    void Show()
    {
        for(int i=0;i<=m;i++)
            cout<<get(i)<<" ";
        cout<<endl;
    }
};
完整的代码在ideone上。。百度放不下囧。。。
http://www.ideone.com/0mrgG