#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<stdlib.h>
using namespace std;
int **c,*a;
char *s;
int len,n;
template<class T>
class Queue;
class OutOfBounds
{
public:
    OutOfBounds(){}
};
template<class T>
class Node{
    friend Queue<T>;
    private:
        T data;
        Node<T> * next;
};
template<class T>
class Queue{
    public:
        Queue(){front=rear=0;}
        ~Queue();
        bool Empty() const
        {
            return (front==rear);
        }

        Queue<T>& EnQueue(const T& x);
        Queue<T>& DeQueue(T& x);
    private:
        Node<T> * front;
        Node<T> * rear;
};
template<class T>
Queue<T>:: ~Queue()
{
    Node<T> * next;
    while(front)
    {
        next=front->next;
        delete front;
        front=next;
    }
}

template<class T>
Queue<T>& Queue<T>::EnQueue(const T& x)
{
    Node<T> *p=new Node<T>;
    p->data=x;
    p->next=0;
    if(front)
        rear->next=p;
    else front=p;
    rear=p;
    return *this;
}
template<class T>
Queue<T>& Queue<T>::DeQueue(T& x)
{
    if(Empty()) throw OutOfBounds();
    x=front->data;
    Node<T> *p=front;
    front=front->next;
    delete p;
    return *this;
}

class QueueNode
{
   
    friend int move(int );
private:
        int level;
        int space;
        int ball;        
};


void compute(int t)         //compute c[i][j]
{
    for(int i=1;i<t;i++)
    {
        c[i][0]=1;
        c[i][1]=i;
        c[i][i-1]=i;
        c[i][i]=1;
        for(int j=2;j<i-1;j++)
            c[i][j]=c[i-1][j-1]+c[i-1][j];
    }     
}
int init()      //delete space,search place of a and space
{
    int j=-1,i,t=1;
    for(i=0;i<2*n;i++)
    {
        if(s[i]=='.')  
        {
            j=i;
            break;
        }
        if(s[i]=='a') a[t++]=i;
    }
    for(i=j;i<2*n-2;i++)
    {
        s[i]=s[i+2];
        if(s[i]=='a') a[t++]=i;
    }
    return j;
}
int change(int *aa)       //change string to int
{
   aa[0]=-1;
   int i,j,value=0;
   for(i=1;i<n;i++)
      for(j=aa[i-1]+1;j<aa[i];j++)
          value+=c[len-j][n-1-i];
   return value;
}
void changeback(int v,int *aa)
{
    aa[0]=-1;
    int i=1,j=0,d;
    while(i<n)
    {
        d=v-c[len-j][n-1-i];
        if(d>=0)
        {
            v=d;
            j++;
        }
        else aa[i++]=j++;
    }
}
int move(int space)
{
    int t=change(a);
    if(t==0) return 0;
    int sf,i,j,l,lev=0,sp=space,number=1;
    for(i=2;i<=n;i++)
        number+=c[2*n-i][n-2];

    int *v=new int[number];
    for(i=0;i<number;i++)
        v[i]=0;

    Queue<QueueNode> Q;
    QueueNode N;
    int *aa=new int [n];

    while(true)
    {
        changeback(t,aa);
        sf=n;
        for(i=1;i<n;i++)    //search the first a after space
        {
            if(aa[i]>=sp)  
            {
                sf=i;
                break;
            }
        }

        bool *m=new bool[len];
        for(i=0;i<len;i++)
        {
            m[i]=true;
        }
        m[len-1]=false;            // ball can not move
        if(sp>0) m[sp-1]=false;
        
        for(i=1;i<n;i++)   // the first moveball is a
        {
            if(m[aa[i]])
            {
                m[aa[i]]=false;
                int *bb=new int[n];
                for(l=1;l<n;l++)
                   bb[l]=aa[l];
                     
                if(i<sf)              // move right
                {
                    N.space=aa[i];
                    bb[i]=sp-2;
                    j=i+1;
                    if(j<sf && aa[j]==aa[i]+1) // the moveballs is aa
                    {
                        bb[j]=sp-1;
                        j++;
                    }
                    while(j<sf) bb[j++]-=2;               
                }
                else         // move left
                {
                    N.space=aa[i]+2;
                    bb[i]=sp;
                    if(i<n-1 && aa[i+1]==aa[i]+1) bb[i+1]=sp+1; // the moveballs is aa
                    for(j=sf;j<i;j++)
                        bb[j]+=2;
                }

                sort(bb+1,bb+n);
                t=change(bb);
                delete []bb;
                if(t==0)           //find the result
                {
                    delete []v;
                    delete []aa;
                    return lev+1;
                }

                if(!(v[t] & (1<<N.space)))
                {                          //have not reach this state
                    v[t]|= (1<<N.space);
                    N.ball=t;
                    N.level=lev+1;
                    Q.EnQueue(N);
                }
           
            }
        }
        // the first moveball is b
        j=1;
        for(i=0;i<len;i++)
        {
            if(m[i])
            {
                while(j<n && aa[j]<i) j++;
                int *bb=new int[n];
                for(l=1;l<n;l++)
                    bb[l]=aa[l];
                if(i<sp)            //move right
                {
                    N.space=i;
                    if(j<n && aa[j]==i+1) // the moveballs is ba
                    {
                        bb[j]=sp-1;
                        l=j+1;
                    }
                    else l=j;
                    while(l<sf) bb[l++]-=2;
                }
                else                   //move left
                {
                    N.space=i+2;
                    if(j<n && aa[j]==i+1) bb[j]=sp+1;// the moveballs is ba
                    for(l=sf;l<j;l++)
                        bb[l]+=2;   
                }

                sort(bb+1,bb+n);
                t=change(bb);
                delete []bb;
                if(t==0)     //find the result
                {
                    delete []v;
                    delete []aa;
                    return lev+1;
                }

                if(!(v[t] & (1<<N.space)))
                {
                    v[t]|= (1<<N.space);
                    N.ball=t;
                    N.level=lev+1;
                    Q.EnQueue(N);
                }
            }
        }
        delete []m;
        if(Q.Empty()) break;
        Q.DeQueue(N);
        lev=N.level;
        sp=N.space;
        t=N.ball;
    }

    delete []v;
    delete []aa;
    return -1;
}
void main()
{
    int k,i;
    cin>>k;
    while(k>0)
    {

        cin>>n;
        s=new char[2*n];
        i=0;
        cin.get();
        char t;
        while(cin.get(t)&&t!='\n')
        {
            s[i++]=t;
        }
        if(i<2*n) cout<<"No Solution"<<endl;
        else
        {
            len=2*n-2;
            int q=len+1;
            c=new int *[q];
            for(i=0;i<q;i++)
                c[i]=new int [q];
            compute(q);
            a=new int[n];
            int space=init();
            i=move(space);
            
            if(i<0) cout<<"No Solution"<<endl;
            else cout<<i<<endl;
            for(i=0;i<q;i++)
                delete [] c[i];
            delete []c;
        }
        delete []s;
        k--;
    }

}

能否在此基础上,对期间的程序用其他语句代替实现,优化?算法不变!