学步园

思路简单，把状态看成一个长十五的01串，总状态为(2^15)，以判断每个小球可否转移，转移的费时接近(3*11*4)大概最坏七八百万算法；总共输入为1-15打表可过；

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn = 16;

vector<int> a[maxn][7];
int deg[maxn],n;
const int b[11][6]={
{1,2,4,7,11},
{3,5,8,12},
{6,9,13},
{10,14},
{2,3},
{4,5,6},
{7,8,9,10},
{1,3,6,10,15},
{2,5,9,14},
{4,8,13},
{7,12}
};
void init(){
for(int i=1;i<=15;i++){

           int& cnt=deg[i];
           cnt=0;
           for(int j=0;j<11;j++){
                for(int k=0;k<6;k++){
                      if(b[j][k]==i){
                           if(b[j][k+1]!=0){
                               for(int p=k+1;b[j][p]!=0;p++)
                                  a[i][cnt].push_back(b[j][p]);
                                  cnt++;
                           }
                      }
                }
           }

            for(int j=0;j<11;j++){
                for(int k=4;k>=0;k--){
                      if(b[j][k]==i){
                           if(k>0){
                               for(int p=k-1;p>=0;p--)
                                  a[i][cnt].push_back(b[j][p]);
                                  cnt++;
                           }
                      }
                }
            }
}
}
void show(int s){
for(int i=14;i>=0;i--) if((s>>i)&1) cout<<"1";
else cout<<"0";
cout<<endl;
}
const  int N = (1<<15)+2;
struct node{
int from,to;
node(int a=0,int b=0) :from(a),to(b){}
bool operator < (const node& rhs)const{
return from < rhs.from ||from == rhs.from && to<rhs.to;}
};
node act[N];
int vis[N],S,goal_state,q[N*10],dist[N];
int bfs(){
int s =((1<<15)-1)&(~(1<<(S-1)));
for(int i=0;i<(1<<15);i++) vis[i]=10000;
for(int i=0;i<(1<<15);i++) act[i]=node(16,16);
show(s);
q[0]=s; vis[s]=0;
dist[0]=-1;
int front_=0,rear=1;
while(front_<rear){
      int& u = q[front_];
      if(u == goal_state){
            return vis[u];
      }
      for(int i=0;i<15;i++) if((u>>i)&1){

            for(int j=0;j<deg[i+1];j++){

                int ok=0;
                for(int k=0;k<a[i+1][j].size();k++){
                     if(!((u>>(a[i+1][j][k]-1))&1)) {ok=1; break;}
                }

                int& v=q[rear]; v=u;

                if(ok){
                    v=v&(~(1<<(i)));
                    int posi ;
                    for(int k=0;k<a[i+1][j].size();k++){
                     if(!((v>>(a[i+1][j][k]-1))&1)){
                             v|=1<<(a[i+1][j][k]-1); posi=a[i+1][j][k];
                             break;
                     }
                     else v=v&(~(1<<(a[i+1][j][k]-1)));
                    }
                     if(vis[v]>vis[u]+1 || vis[v]==vis[u]+1 && node(i+1,posi)<act[v]){
                            dist[v]= u;
                            act[v] = node(i+1,posi);
                            vis[v] =vis[u]+1;
                            rear++;
                     }
                }
            }
      }
      front_++;
}
return -1;
}

int main()
{
    init();
    int T;
    scanf("%d",&T);
    while(T--){
          scanf("%d",&S);
          goal_state =(1<<(S-1));
          int ans = bfs();
          if(ans == -1) {printf("IMPOSSIBLE\n"); continue;}
          else printf("%d\n",ans);
          print_ans(goal_state);
    }
    return 0;

}