最短手数が４５手までの15パズルが何種類か与えられるので
盤面から最短手数をこたえる問題。
ビット演算にダイクストラ法にマンハッタン距離による枝刈りに両側探索。
自分の知っているすべてのテクを投入したがあまり早くならなかった。
何とか合格できただけ。
やっぱ俺競技プログラムの世界でも底辺なんだ、、、
#include<stdio.h>
#include<map>
#include<iostream>
#include<stdlib.h>
#include<queue>
#include<algorithm>
#include<set>
std::map<unsigned __int64,int> memo2;
const int LIMIT=19;
int xs[16]={3, 0,1,2,3, 0,1,2,3, 0,1,2,3, 0,1,2};
int ys[16]={3, 0,0,0,0, 1,1,1,1, 2,2,2,2, 3,3,3};
int m(unsigned __int64 e1){
unsigned __int64 b=15;
int slide=0;
int sum=0;
for(int i=3;i>=0;i--){
for(int j=3;j>=0;j--){
unsigned __int64 n=((e1>>slide)&b);
if(n>0){
sum+=abs(i-ys[(int)n])+abs(j-xs[(int)n]);
}
slide+=4;
}
}
return sum;
}
struct E{
unsigned __int64 e;
int no;
bool operator<(const E& e1)const{
int a=m(e)+no;
int b=m(e1.e)+e1.no;
if(a!=b)return a>b;;
return no>e1.no;
}
};
std::set<unsigned __int64> memo[30];
std::map<unsigned __int64,int> memo3;
void move(unsigned __int64 e,std::map<unsigned __int64,int>& m0,std::set<unsigned __int64>& m2) {
unsigned __int64 s=15;
int i,j;
bool hit=false;
for(i=3;i>=0;i--){
for(j=3;j>=0;j--){
if((s&e)==0){
hit=true;
break;
}
s=(s<<4);
}
if(hit==true)break;
}
unsigned __int64 e2;
unsigned __int64 p1;
if(i>0){
//??????
p1=((s<<16)&e);
e2=(e|(p1>>16))^p1;
if(m0.find(e2)==m0.end()){
m2.insert(e2);
}
}
if(i<3){
//??????
p1=((s>>16)&e);
e2=(e|(p1<<16))^p1;
if(m0.find(e2)==m0.end()){
m2.insert(e2);
}
}
if(j>0){
//??????
p1=((s<<4)&e);
e2=(e|(p1>>4))^p1;
if(m0.find(e2)==m0.end()){
m2.insert(e2);
}
}
if(j<3){
//??????
p1=((s>>4)&e);
e2=(e|(p1<<4))^p1;
if(m0.find(e2)==m0.end()){
m2.insert(e2);
}
}
}
int main(){
unsigned __int64 seed=0,j=4;
for(unsigned __int64 i=15;i>=1;i--){
seed=(seed|(i<<j));
j+=4;
}
memo[0].insert(seed);
memo2[seed]=0;
std::set<unsigned __int64>::iterator it;
for(int i=0;i<LIMIT;i++){
for(it=memo[i].begin();it!=memo[i].end();it++){
if(i==0){
move((*it),memo2,memo[1]);
}else{
move((*it),memo2,memo[i+1]);
}
}
for(it=memo[i+1].begin();it!=memo[i+1].end();it++){
memo2[(*it)]=i+1;
}
if(i>1)memo[i-1].clear();
//std::cout<<i<<" "<<memo2.size()<<"\n";
}
int slide=64;
unsigned __int64 p=0;
unsigned __int64 n=0;
for(int i=0;i<16;i++){
slide-=4;
std::cin>>n;
p=(p|(n<<slide));
}
std::priority_queue<E> pq;
E e3;
e3.e=p;
e3.no=0;
pq.push(e3);
int ans=100;
while(pq.empty()==false){
e3=pq.top();
pq.pop();
if(memo2.find(e3.e)!=memo2.end()){
ans=std::min(memo2[e3.e]+e3.no,ans);
continue;
}
if(memo3.find(e3.e)!=memo3.end()){
continue;
}
memo3[e3.e]=e3.no;
if(e3.no+LIMIT>=ans)continue;
if(m(e3.e)+e3.no>=ans)continue;
unsigned __int64 e=e3.e,p1,e2;
E e4;
unsigned __int64 s=15;
int i,j;
bool hit=false;
for(i=3;i>=0;i--){
for(j=3;j>=0;j--){
if((s&e)==0){
hit=true;
break;
}
s=(s<<4);
}
if(hit==true)break;
}
if(hit==false){
printf("out");
}
if(i>0){
//??????
p1=((s<<16)&e);
e2=(e|(p1>>16))^p1;
e4.e=e2;
e4.no=e3.no+1;
if(memo3.find(e4.e)==memo3.end()){
pq.push(e4);
}
}
if(i<3){
//??????
p1=((s>>16)&e);
e2=(e|(p1<<16))^p1;
e4.e=e2;
e4.no=e3.no+1;
if(memo3.find(e4.e)==memo3.end()){
pq.push(e4);
}
}
if(j>0){
//??????
p1=((s<<4)&e);
e2=(e|(p1>>4))^p1;
e4.e=e2;
e4.no=e3.no+1;
if(memo3.find(e4.e)==memo3.end()){
pq.push(e4);
}
}
if(j<3){
//??????
p1=((s>>4)&e);
e2=(e|(p1<<4))^p1;
e4.e=e2;
e4.no=e3.no+1;
if(memo3.find(e4.e)==memo3.end()){
pq.push(e4);
}
}
}
printf("%d\n",ans);
return 0;
}
最終更新：2015年12月20日 08:15
