接續15-puzzle(一)，後來又查到了
這篇文章，他的IDA* 寫法跟我的不太一樣，而且又可以估計下一次的 maxdep 應該要取多少比較好，所以我就照著他的方法寫，但是覺得那個 114/100 真是太詭異了先不理他，果然執行時間會比上一個 code 還要短，但傳到 ZJ 還是 TLE 了，後來我才領悟那個 114/100 的精髓(?)，不過感覺還蠻唬爛的XD 剪掉了一些不太可能是檞但又有可能是解的狀態XDD 後來我試著把常數亂改( 加減幾個 1/100 之類的 ) ，發現大部分的情形都還是會TLE，或是如果常數在大一點會WA ( 因為把正解的狀態剪掉了 )， 114/100 真是一個剛好的值.....而且加了這個之後竟然比原本不乘這個常數跑的速度快了5~10倍左右......真是太強大啦!!!! XD
附上 AC了 ZJ d207 的 code ，但很詭異的是傳到UVa 竟然會TLE......怎麼想都沒道理阿OAO，不過AC就是AC啦XD(哪招
code :
#include<bits/stdc++.h>
using namespace std;
int a0[35][4]={ {0,0,0,4},{0,0,1,3},{0,0,2,2},{0,0,3,1},{0,0,4,0},
{0,1,0,3},{0,1,1,2},{0,1,2,1},{0,1,3,0},{0,2,0,2},{0,2,1,1},{0,2,2,0},
{0,3,0,1},{0,3,1,0},{0,4,0,0},{1,0,0,3},{1,0,1,2},{1,0,2,1},{1,0,3,0},
{1,1,0,2},{1,1,1,1},{1,1,2,0},{1,2,0,1},{1,2,1,0},{1,3,0,0},{2,0,0,2},
{2,0,1,1},{2,0,2,0},{2,1,0,1},{2,1,1,0},{2,2,0,0},{3,0,0,1},{3,0,1,0},
{3,1,0,0},{4,0,0,0} } ;
int b0[20][4]={ {0,0,0,3},{0,0,1,2},{0,0,2,1},{0,0,3,0},{0,1,0,2},
{0,1,1,1},{0,1,2,0},{0,2,0,1},{0,2,1,0},{0,3,0,0},{1,0,0,2},{1,0,1,1},
{1,0,2,0},{1,1,0,1},{1,1,1,0},{1,2,0,0},{2,0,0,1},{2,0,1,0},{2,1,0,0},
{3,0,0,0} } ;
struct P
{
int x,y,z ;
bool operator < (const P &rhs) const
{
if(x!=rhs.x) return x<rhs.x ;
if(y!=rhs.y) return y<rhs.y ;
return z<rhs.z ;
}
};
struct state
{
int a[16] ;
int zero ;
bool scan()
{
if(scanf("%d",&a[0])==EOF) return 0 ;
zero=0 ;
for(int i=1;i<16;i++)
{
scanf("%d",&a[i]) ;
if(!a[i]) zero=i ;
}
return 1 ;
}
};
int __d[1500000] ;
struct WalkingDistance
{
int cod[5] ;
map<P,int> mpa,mpb ;
int encode()
{
int ret=0 ;
for(int i=0;i<4;i++) ret=ret*35+cod[i] ;
return ret ;
}
void decode(int x)
{
for(int i=0;i<4;i++) cod[3-i]=x%35 , x/=35 ;
}
int num[4][4] ;
void cal()
{
for(int i=0;i<35;i++) mpa[(P){a0[i][0],a0[i][1],a0[i][2]}]=i ;
for(int i=0;i<20;i++) mpb[(P){b0[i][0],b0[i][1],b0[i][2]}]=i ;
queue<int> q ;
memset(__d,-1,sizeof(__d)) ;
int *d = __d ;
cod[0]=mpa[(P){4,0,0}] , cod[1]=mpa[(P){0,4,0}] ,
cod[2]=mpa[(P){0,0,4}] , cod[3]=mpb[(P){0,0,0}] ;
int start=encode() ; d[start]=0 ; q.push(start) ;
while(!q.empty())
{
int u=q.front() ; q.pop() ;
decode(u) ;
int num2[4]={0} ;
for(int i=0;i<4;i++) for(int j=0;j<4;j++)
num[i][j]= i==3 ? b0[cod[i]][j] : a0[cod[i]][j] ,
num2[j]+=num[i][j] ;
int emp ;
for(emp=0;emp<4 && num2[emp]==4;emp++) ;
for(int i=-1;i<=1;i+=2) if(emp+i>=0 && emp+i<4)
for(int j=0;j<4;j++) if(num[j][emp+i])
{
num[j][emp+i]-- ;
num[j][emp]++ ;
for(int z=0;z<4;z++) cod[z]= z==3 ?
mpb[(P){num[z][0],num[z][1],num[z][2]}] :
mpa[(P){num[z][0],num[z][1],num[z][2]}] ;
int newu=encode() ;
if(d[newu]==-1) d[newu]=d[u]+1 , q.push(newu) ;
num[j][emp+i]++ ;
num[j][emp]-- ;
}
}
}
int get_wd(const state &s)
{
int ret=0 ;
memset(num,0,sizeof(num)) ;
for(int i=0;i<16;i++) if(s.a[i])
num[(s.a[i]-1)/4][i/4]++ ;
for(int z=0;z<4;z++) cod[z]= z==3 ?
mpb[(P){num[z][0],num[z][1],num[z][2]}] :
mpa[(P){num[z][0],num[z][1],num[z][2]}] ;
ret+=__d[encode()] ;
memset(num,0,sizeof(num)) ;
for(int i=0;i<16;i++) if(s.a[i])
num[(s.a[i]-1)%4][i%4]++ ;
for(int z=0;z<4;z++) cod[z]= z==3 ?
mpb[(P){num[z][0],num[z][1],num[z][2]}] :
mpa[(P){num[z][0],num[z][1],num[z][2]}] ;
ret+=__d[encode()] ;
return ret ;
}
void set_num(const state &s,int type)
{
memset(num,0,sizeof(num)) ;
for(int i=0;i<16;i++) if(s.a[i])
{
if(type==1) num[(s.a[i]-1)/4][i/4]++ ;
else num[(s.a[i]-1)%4][i%4]++ ;
}
}
int get_wd()
{
for(int z=0;z<4;z++) cod[z]= z==3 ?
mpb[(P){num[z][0],num[z][1],num[z][2]}] :
mpa[(P){num[z][0],num[z][1],num[z][2]}] ;
return __d[encode()] ;
}
}wd1,wd2;
bool check(const state &s)
{
int x=0,pos=0 ;
for(int i=0;i<16;i++)
{
if(s.a[i]) for(int j=i+1;j<16;j++)
{
if(s.a[j] && s.a[j]<s.a[i])
x++ ;
}
else pos=i ;
}
x+=(pos/4) ;
return x%2 ;
}
state st ;
int dx[]={1,0,0,-1} , dy[]={0,1,-1,0} ;
int solved,maxdep ;
char ch[]={'D','R','L','U'} , path[100] ;
int iddfs(int dep,int val1,int val2,int pre)
{
if(!(val1+val2))
{
solved = dep ;
return dep ;
}
if(dep + (val1+val2)*114/100 > maxdep)
return dep+(val1+val2)*114/100 ;
int z=st.zero , x=z/4 , y=z%4 ;
int submaxd = 0xfff ;
for(int i=0;i<4;i++) if(i+pre!=3)
{
int nx=x+dx[i] , ny=y+dy[i] ;
if(nx<0||nx>3||ny<0||ny>3) continue ;
int nz=4*nx+ny ;
int newval1=val1,newval2=val2 ;
if(x!=nx)
wd1.num[(st.a[nz]-1)/4][nx]-- , wd1.num[(st.a[nz]-1)/4][x]++ ,
newval1 = wd1.get_wd() ;
else
wd2.num[(st.a[nz]-1)%4][ny]-- , wd2.num[(st.a[nz]-1)%4][y]++ ,
newval2 = wd2.get_wd() ;
swap(st.a[z],st.a[nz]) ; st.zero=nz ;
path[dep]=ch[i] ;
int tmp=iddfs(dep+1,newval1,newval2,i) ;
swap(st.a[z],st.a[nz]) ; st.zero=z ;
if(x!=nx)
wd1.num[(st.a[nz]-1)/4][nx]++ , wd1.num[(st.a[nz]-1)/4][x]-- ;
else
wd2.num[(st.a[nz]-1)%4][ny]++ , wd2.num[(st.a[nz]-1)%4][y]-- ;
if(solved) return solved ;
submaxd=min(submaxd,tmp) ;
}
return submaxd ;
}
main()
{
wd1.cal() ; wd2.cal() ;
int T ; scanf("%d",&T) ;
while(T--)
{
st.scan() ;
int start=clock() ;
if(!check(st))
{ printf("This puzzle is not solvable.\n") ; continue ; }
wd1.set_num(st,1) ;
wd2.set_num(st,2) ;
solved=0 ;
int val1,val2 ;
val1=wd1.get_wd() ;
val2=wd2.get_wd() ;
maxdep=val1+val2 ;
while(!solved)
{
// printf("now depth = %d\n",maxdep) ;
maxdep = iddfs(0,val1,val2,-1) ;
}
printf("%d",solved) ;
// for(int i=0;i<maxdep;i++) printf("%c",path[i]) ;
printf("\n") ;
// int end=clock() ;
// printf("total use %.4f s \n",((double)(end-start))/CLOCKS_PER_SEC) ;
}
}
