| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
单向BFS AC! 贴代码#include <cstdio>
#include <string.h>
#include <queue>
#include <stack>
//#include <ctime>
using namespace std;
const int mul[10]={1,1,2,6,24,120,720,5040,40320,362880};
int A[9],A1[9];
bool use[9],hash[362880];
int f(int *a) {
memset(use,0,sizeof(use));
int ret=0;
for(int i=8;i>=0;i--) {
int cnt=0;
for(int j=0;j<a[8-i];j++) if(!use[j])cnt++;
ret+=cnt*mul[i];use[a[8-i]]=1;
}
return ret;
}
void f1(int a1) {
int ret=a1,tmp;
memset(use,0,sizeof(use));
for(int i=8;i>=0;i--) {
tmp=ret/mul[i];
int a=0,p=-1;
while(a<tmp) {
p++;
if(!use[p]) a++;
}
p++;
while(use[p]) p++;
A1[8-i]=p;
use[p]=1;
ret%=mul[i];
}
}
/*void Tester() {
scanf("%d",&N);
for(int i=0;i<N;i++) {
for(int j=0;j<9;j++) scanf("%d",A+j);
printf("%d\n",f());
}
scanf("%d",&N);
for(int i=0;i<N;i++) {
scanf("%d",A);
f1();
}
}*/
queue<int> Q;
queue<queue<char> > Q1;
int path[362880],move[362880];
inline int m(int x,int y) {return x*3+y;}
void BFS() {
bool flag1=0;
//queue<char> tmp1;
//while(!tmp1.empty()) tmp1.pop();
while(!Q.empty()) Q.pop();
int tmp=f(A),tmp1;
Q.push(tmp);hash[tmp]=1;path[tmp]=-1;
while(!Q.empty()) {
tmp=Q.front();Q.pop();tmp1=tmp;
//tmp1=Q1.front();Q1.pop();
f1(tmp);
bool flag=1;
for(int i=0;i<8;i++)if(A1[i]!=i+1){flag=0;break;}
if(flag) {
stack<char> S;
while(path[tmp]!=-1) {S.push(move[tmp]);tmp=path[tmp];}
while(!S.empty()) {printf("%c",S.top());S.pop();}
puts("");flag1=1;
break;
}
int x,y;
for(x=0;x<3;x++) {
for(y=0;y<3;y++)if(!A1[m(x,y)]) break;
if(y<3) break;
}
if(x>0) {
swap(A1[m(x,y)],A1[m(x-1,y)]);
tmp=f(A1);
if(!hash[tmp]){hash[tmp]=1;Q.push(tmp);path[tmp]=tmp1;move[tmp]='u';}
swap(A1[m(x,y)],A1[m(x-1,y)]);
}
if(x<2) {
swap(A1[m(x,y)],A1[m(x+1,y)]);
tmp=f(A1);
if(!hash[tmp]){hash[tmp]=1;Q.push(tmp);path[tmp]=tmp1;move[tmp]='d';}
swap(A1[m(x,y)],A1[m(x+1,y)]);
}
if(y>0) {
swap(A1[m(x,y)],A1[m(x,y-1)]);
tmp=f(A1);
if(!hash[tmp]){hash[tmp]=1;Q.push(tmp);path[tmp]=tmp1;move[tmp]='l';}
swap(A1[m(x,y)],A1[m(x,y-1)]);
}
if(y<2) {
swap(A1[m(x,y)],A1[m(x,y+1)]);
tmp=f(A1);
if(!hash[tmp]){hash[tmp]=1;Q.push(tmp);path[tmp]=tmp1;move[tmp]='r';}
swap(A1[m(x,y)],A1[m(x,y+1)]);
}
}
if(!flag1) puts("unsolvable");
}
int main()
{
//Tester();
char buf[2];
for(int i=0;i<9;i++) {
scanf("%s",buf);
if(buf[0]=='x') A[i]=0;
else A[i]=buf[0]-'0';
}
//int c=clock();
BFS();
//int t=clock()-c;
//printf("%d\n",t);
//getchar();getchar();getchar();getchar();
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator