BFS练习(附带hash算法)
这个代码真的看的好久，不是我自己写的，但是陌生的东西太多了，孩怕啊。
#include<cstdio>
#include<cstring>
#include<set>
using namespace std;
typedef int State[9];//定义“状态类型”
const int maxstate=1000000;
State st[maxstate],goal;//状态数组。所有状态都保存在这里
int dist[maxstate]; //距离数组
const int dx[]={-1,1,0,0};
const int dy[]={0,0,-1,1};
//BFS,返回目标状态在st数组下标
//编码与解码
set<int> vis;
void init_lookup_table()
{
vis.clear();
}
int try_to_insert(int s)
{
int v=0;
for(int i=0;i<9;i++)
v=v*10+st[s][i];
if(vis.count(v)) return 0;
vis.insert(v);
return 1;
}
int bfs()
{
init_lookup_table(); //初始化查找表
int front=1,rear=2;//不使用下标0，因为0被看作"不存在",front为队首指针，rear为队尾指针，因为要符合前闭后开的习惯
while(front<rear)//队列不为空
{
State& s=st[front]; //用“引用”来简化代码
if(memcmp(goal,s,sizeof(s))==0) return front;//找到目标状态，成功返回
int z;
for(z=0;z<9;z++) if(!s[z]) break;
int x=z/3,y=z%3; //获取行列编号
for(int d=0;d<4;d++)
{
int newx=x+dx[d];
int newy=y+dy[d];
int newz=newx*3+newy;
if(newx>=0&&newy<3&&newy>=0&&newx<3)//若移动合法
{
State& t=st[rear]; //扩展新结点
memcpy(&t,&s,sizeof(s));
t[newz]=s[z];
t[z]=s[newz];//交换移动的元素
dist[rear]=dist[front]+1;//更新结点的距离值
if(try_to_insert(rear)) rear++;//如果成功插入查找表，修改队尾指针
}
}
front++;
}
return 0;
}
int main()
{
for(int i=0;i<9;i++)
scanf("%d",&st[1][i]);
for(int i=0;i<9;i++)
scanf("%d",&goal[i]);
int ans=bfs();
if(ans>0) printf("%d",dist[ans]);
else printf("-1\n");
return 0;
}
/*
编码与解码的另两种写法
1.
int vis[362880],fact[9];
void init_lookup_table()
{
fact[0]=1;
for(int i=1;i<9;i++)
fact[i]=fact[i-1]*i;
}
int try_to_insert(int s)
{
int code=0;//st[s]映射到整数code
for(int i=0;i<9;i++)
{
int cnt;
for(int j=i+1;j<9;j++)
if(st[s][j]<st[s][i]) cnt++;
code+=fact[8-i]*cnt;
}
if(vis[code]) return 0;
return vis[code]=1;
}
2.hash技术
const int hashsize=1000003;
int head[hashsize],next[maxstate]={0};
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;//确保hash函数值是不超过hash表的大小的非负整数
}
int try_to_insert(int s)
{
int h=hash(st[s]);//h记录编码值
int u=head[h];
while(u)//若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;
}
*/
大概说一下几个要点
dx，dy两个数组，分别模拟四个方向的走动，这个要好好学习，我记得之前我好像是用一堆堆判断来写的，实在蠢死了。
作者是用数组来模拟队列，队列模拟需要一个线性表和一个头指针，一个尾指针。
hash算法：先将一段信息通过编码（这个必须是个双射）得到一个大整数，然后对大整数取模来缩小这个数据，此时有可能获得多段信息hash值相等，此时将hash值相等的所有信息连成链表，当遇到hash值相等的信息时，直接比较本来的信息，否则直接比较hash值即可判重。
还有引用的用法，这里不详细解释了
当你debug