Bfs + Hash is ok.
I found that the functions named mem... are veru useful.
Here is my code:
#include<iostream>
#include<string.h>
#define maxn 1000000
using namespace std;
const int xd[]={-1,1,0,0},yd[]={0,0,-1,1};
int st[maxn][3][3],front=1,rear=1,aim[3][3]={{1,2,3},{8,0,4},{7,6,5}},dist[maxn];
int head[maxn],next[maxn];
long hash(long x)
{
long re=0;
for(long i=0;i<3;i++)
for(long j=0;j<3;j++)
re=(re*10+st[x][i][j])%maxn;
return re;
}
void insert(long x)
{
long h=hash(x),p=head[h];
while(p)
{
if(memcmp(st[p],st[x],sizeof(st[p]))==0) return;
p=next[p];
}
next[x]=head[h];head[h]=x;
rear++;dist[rear]=dist[front]+1;
}
long bfs()
{
while(front<=rear)
{
if(memcmp(st[front],aim,sizeof(aim))==0) return front;
// Found answer , return the position of the final state
long x,y;
bool find_zero=false;
for(x=0;x<3&&!find_zero;x++)
for(y=0;y<3&&!find_zero;y++)
if(st[front][x][y]==0)
find_zero=true;
x--;y--;
// Find the position of figure zero
for(long k=0;k<4;k++)
{
long newx=x+xd[k],newy=y+yd[k];
if(newx>=0&&newx<3&&newy>=0&&newy<3)
{
memcpy(st[rear+1],st[front],sizeof(st[front]));
st[rear+1][x][y]=st[rear+1][newx][newy];
st[rear+1][newx][newy]=0;
// Produce new states
insert(rear+1);
// Try to insert
}
}
front++;
}
return -1;
}
int main()
{
string s;
cin>>s;
for(long i=0;i<3;i++)
for(long j=0;j<3;j++)
st[1][i][j]=s.at(3*i+j)-'0';
dist[1]=0;
// Input
long ans=bfs();
// Bfs
cout<<dist[ans]<<endl;
// Output
return 0;
}
posted on 2010-09-22 10:26
lee1r 閱讀(405)
評論(0) 編輯 收藏 引用 所屬分類:
題目分類：搜索