POJ 1077 (HDU 1043) Eight (8 야드 DBFS)
3869 단어 데이터 구조: BFS
//
// main.cpp
// Richard
//
// Created by on 16/9/11.
// Copyright © 2016 . All rights reserved.
//
#include
#include
#include
#include
#include
using namespace std;
const int maxn=400000;
int ha[9]={1,1,2,6,24,120,720,5040,40320};
int End[9]={1,2,3,4,5,6,7,8,0};
char result[maxn];
struct node{
int sta[9];
int fa;
char move;
int hash;
node(int fa,char move,int hash):fa(fa),move(move),hash(hash) {};
node() {};
};
node myQueue[2][maxn];
int qHead[2],qTail[2];
char moves[5]="uldr";
int dx[4]={-1,0,1,0};
int dy[4]={0,-1,0,1};
int matchingstatus;
int matchingQ;
int contor(int a[9])
{
int res=0,k;
for(int i=0;i<9;i++)
{
k=0;
for(int j=i+1;j<9;j++)
{
if(a[i]>a[j]) k++;
}
res+=k*ha[9-i-1];
}
return res;
}
bool equal(int a[9])
{
int times=0;
for(int i=0;i<9;i++)
{
if(a[i]==0) continue;
for(int j=i+1;j<9;j++)
{
if(a[j]==0) continue;
if(a[i]>a[j]) times++;
}
}
return times&1;
}
bool inside(int x,int y)
{
return x<0||x>2||y<0||y>2;
}
bool DBFS(int a[9])
{
set expand[2];
int starthash=contor(a);
int endhash=contor(End);
for(int i=0;i<2;i++){
qHead[i]=0;qTail[i]=1;
}
myQueue[0][0]=node(-1,0,starthash);
for(int i=0;i<9;i++) myQueue[0][0].sta[i]=a[i];
expand[0].insert(starthash);
myQueue[1][0]=node(-1,0,endhash);
for(int i=0;i<9;i++) myQueue[1][0].sta[i]=End[i];
expand[1].insert(endhash);
int qNo,vqNo;
while(qHead[0]!=qTail[0]||qHead[1]!=qTail[1])
{
if(qHead[0]==qTail[0]) qNo=1;
else if(qHead[1]==qTail[1]) qNo=0;
else{
if(qTail[0]-qHead[0]<=qTail[1]-qHead[1]) qNo=0;
else qNo=1;
}
vqNo=1-qNo;
node now=myQueue[qNo][qHead[qNo]];
if(expand[vqNo].find(now.hash)!=expand[vqNo].end())
{
matchingstatus=now.hash;
matchingQ=qNo;
return true;
}
else{
for(int i=0;i<4;i++)
{
int pos;
for(int j=0;j<9;j++)
if(now.sta[j]==0) {pos=j;break;}
int x=pos/3+dx[i],y=pos%3+dy[i];
if(inside(x,y)) continue;
int npos=x*3+y;
memcpy(a,now.sta,sizeof(int)*9);
swap(a[pos],a[npos]);
node next(qHead[qNo],moves[i],contor(a));
memcpy(next.sta,a,sizeof(int)*9);
if(expand[qNo].find(next.hash)!=expand[qNo].end()) continue;
expand[qNo].insert(next.hash);
myQueue[qNo][qTail[qNo]]=next;
qTail[qNo]++;
}
qHead[qNo]++;
}
}
return false;
}
inline char ReverseMove(char c) {
if(c=='u') return 'd';
if(c=='d') return 'u';
if(c=='l') return 'r';
if(c=='r') return 'l';
return 0;
}
int main()
{
char buf[100];
while(gets(buf))
{
int a[9],k=0;
int len=(int)strlen(buf);
for(int i=0;i='1'&&buf[i]<='9') {a[k]=buf[i]-'0';k++;}
}
if(equal(a))
{
printf("unsolvable
");
continue;
}
if(DBFS(a))
{
int move=0;
int pos=0;
if(matchingQ==0) pos=qHead[0];
else{
for(int i=0;i