UVA - 1533 (Moving Pegs)
考え方は簡単で、状態を1つの長い15の01列と見なして、総状態は(2^15)で、各ボールが移動するかどうかを判断して、移動の時間は(3*11*4)大体最悪の7,800万のアルゴリズムに近いです;全部で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
"); continue;}
else printf("%d
",ans);
print_ans(goal_state);
}
return 0;
}