PKU 1178 Camelot
http://poj.org/problem?id=1178
チェス盤の上に一つのキングと何個かのナイトがいる。
全てのコマを一箇所に集めたい。このとき、同じマスに二つ以上コマがあってもいいものとし、さらにナイトはキングと同じコマに止まった時、キングをナイトと一緒に動かすことが出来る。(二つ動かして1手とする)
最低何手動かす必要があるかを求めろというような問題。
集める場所、ナイトとキングの合流地点、キングを運ぶナイトで全探索する。
PKU 800問目。夏休み頑張るつもりだったのに、ついグダグダしてしまって結局あまり解けずに終わりそうなのがわりと残念です。
最盛期のペースを維持できていたらなぁとか思いますが、自業自得ですね。
int tx[]={1,2,2,1,-1,-2,-2,-1},ty[]={2,1,-1,-2,-2,-1,1,2}; int wall[64][64]; main(){ rep(i,64){ rep(j,64)wall[i][j]=64; wall[i][i]=0; } rep(i,64){ int cx=i/8,cy=i%8; rep(j,8){ int nx=cx+tx[j],ny=cy+ty[j]; if(0>nx || nx>=8 || 0>ny || ny>=8)continue; wall[i][nx*8+ny]=1; } } rep(k,64)rep(i,64)rep(j,64)wall[i][j]=min(wall[i][j],wall[i][k]+wall[k][j]); string in; cin>>in; int pos[64]; rep(i,SZ(in)/2)pos[i]=(in[i*2]-'A')*8+in[i*2+1]-'1'; int ans=1<<28; rep(i,64){ int tans=0; rep(k,SZ(in)/2-1)tans+=wall[i][pos[k+1]]; rep(j,64){ rep(k,SZ(in)/2-1) ans=min(ans, tans+abs(pos[0]/8-j/8)+abs(pos[0]%8-j%8)+ wall[pos[k+1]][j]+wall[j][i]-wall[pos[k+1]][i]); } } cout<<ans<<endl; }