c++
#include<iostream>
#include<cstring>
#define INF 400000
#define hashsize 1000003
using namespace std;
typedef int state[9];
state st[INF];
int goal[9]={1,2,3,8,0,4,7,6,5};
int dist[INF];
int head[hashsize],next[hashsize];
const int dx[4]={-1,1,0,0};
const int dy[4]={0,0,-1,1};
void init_lookup_table(){
memset(head,0,sizeof(head));
}
int hash(state &s){
int v=0;
for(int i=0;i<9;i++){
v+=v*10+s[i];
}
return v%hashsize;
}
bool try_to_insert(int s){
int h=hash(st[s]);
int u=head[h];
while(u){
if(memcmp(st[u],st[s],sizeof(st[s]))==0) return 0;
u=next[u];
}
next[s]=head[h];
head[h]=s;
return 1;
}
int bfs(){
init_lookup_table();
int head=1,tail=2,i;
dist[head]=0;
while(head<tail){
state &s=st[head];
if(memcmp(s,goal,sizeof(goal))==0) return head;
for(i=0;i<9;i++)
if(!s[i]) break;
int z=i;
int x=z/3,y=z%3;
for(i=0;i<4;i++){
int newx=x+dx[i];
int newy=y+dy[i];
int newz=newx*3+newy;
if(0<=newx&&newx<3&&0<=newy&&newy<3){
state &t=st[tail];
memcpy(t,s,sizeof(s));
t[newz]=s[z];
t[z]=s[newz];
dist[tail]=dist[head]+1;
if(try_to_insert(tail)) tail++;
}
}
head++;
}
return 0;
}
int main(){
char a,i;
for(i=0;i<9;i++){
cin>>a;
st[1][i]=a-'0';
}
cout<<dist[bfs()];
return 0;
}
3 条评论
-
benzy LV 8 @ 2017-02-13 10:31:51
hash 是c++11的保留字
-
@ 2016-10-30 21:31:07
我也是，在codevs上能ac，在vijos上就ce
```C++
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=370000;
int n,final,Ans,p;
char a[1000];
int last[MAXN],queue[MAXN],rank[MAXN];
bool visit[MAXN];
int s[9];
int front=1,rear=1;
int turn(){
int i;
int ans=0;
for(i=0;i<9;i++)
ans=ans*10+s[i];
return ans;
}
int cantor(){
bool use[9]={0};
int i,j,no;
int ans=0;
for(i=8;i>=1;i--)
{no=0;
use[s[8-i]]=true;
for( j=0;j<s[8-i];j++)
{if(use[j]==true)
no++;}
ans=(ans+s[8-i]-no)*i;
}return ans;
}
void init(){
int i;
for(i=0;i<9;i++){
s[i]=a[i]-'0';
n=n*10+s[i];
}
queue[1]=n;
visit[cantor()]=true;
n=0;s[0]=1;s[1]=2;s[2]=3;
s[3]=8;s[4]=0;s[5]=4;s[6]=7;s[7]=6;s[8]=5;
final=cantor();
}
void Ucan(int num){
int i;
for(i=8;i>=0;i--){
s[i]=num%10;
num/=10;
}
}
int findzero(){
int i;
for(i=0;i<9;i++)
if(s[i]==0)
return i;
}
void bfs(int c){
int t,num;
t=s[p];s[p]=s[p+c];s[p+c]=t;
num=cantor();
if(visit[num]!=true)
{
queue[++rear]=turn();
visit[num]=true;
rank[rear]=rank[front]+1;
if(num==final)
Ans=rank[front]+1;
}
t=s[p];s[p]=s[p+c];s[p+c]=t;
}
int main()
{gets(a);init();
if(visit[final]==true){
cout<<"0"<<endl;return 0;
}
while(front<=rear&&Ans==0){
Ucan(queue[front]);
p=findzero();
if(p>=3)
bfs(-3);
if(Ans==0&&p<6)
bfs(3);
if(Ans==0&&(p%3)>0)
bfs(-1);
if(Ans==0&&(p%3)<2)
bfs(1);
front++;
}
if(Ans==0)
cout<<"-1"<<endl;
else
cout<<Ans<<endl;return 0;
}
``` -
@ 2016-09-15 21:27:40
把“hash”改为“_hash”试试
- 1
