BFS解决九宫重排问题

如下面第一个图的九宫格中，放着  1~8  的数字卡片，还有一个格子空着。与空格子相邻的格子中的卡片可以移动到空格中。经过若干次移动，可以形成第二个图所示的局面。

12345678. 
123.46758 

3


实现代码如下:
(我用了string来记录已经出现过的排列情况,应该用其它方法储存速度会更快)

#include<string.h>
#include<iostream>
#include<set>
using namespace std;
int main()
{
set<string>s;
string arr[200000];
int front=0;int rear=0;
int dis[200000]={0};
int pos=0;
string beg,des;
cin>>beg>>des;
if(beg==des){cout<<0<<endl;return 0;
}
s.insert(beg);int dalta[4]={-1,1,-3,3};
arr[front]=beg;
while(front<=rear)
{
beg=arr[front];
for(pos=0;pos<9;pos++)if(beg[pos]==‘.‘)break;
for(int i=0;i<4;i++)
{
if(pos==0||pos==1||pos==2)if(i==2)continue;
if(pos==6||pos==7||pos==8)if(i==3)continue;
if(pos==0||pos==3||pos==6)if(i==0)continue;
if(pos==2||pos==5||pos==8)if(i==1)continue;
int p=pos+dalta[i];
char c=beg[pos];beg[pos]=beg[p];beg[p]=c;
if(s.count(beg)==0)
{
s.insert(beg);
arr[++rear]=beg;dis[rear]=dis[front]+1;
if(beg==des)
{
cout<<dis[front]+1<<endl;return 0;
}
}
c=beg[pos];beg[pos]=beg[p];beg[p]=c;
}
front++;
}
cout<<-1<<endl;return 0;
}