PKU1077 八数码，双向广搜+康托展开
http://poj.org/problem?id=1077
思路并不难，只是调的过程中有些问题，懒得写，从高手那转来的
双向广度优先搜索算法是对广度优先算法的一种扩展。广度优先算法从起始节点以广度优先的顺序不断扩展，
直到遇到目的节点；而双向广度优先算法从两个方向以广度优先的顺序同时扩展，一个是从起始节点开始扩展，另
一个是从目的节点扩展，直到一个扩展队列中出现另外一个队列中已经扩展的节点，也就相当于两个扩展方向出现了
交点，那么可以认为我们找到了一条路径。双向广度优先算法相对于广度优先算法来说，由于采用了从两个跟开始扩展
的方式，搜索树的深度得到了明显的减少，所以在算法的时间复杂度和空间复杂度上都有较大的优势！双向广度优先算
法特别适合于给出了起始节点和目的节点，要求他们之间的最短路径的问题。另外需要说明的是，广度优先的顺序能够保证
找到的路径就是最短路径！
基于以上思想，我们给出双向广度优先算法编程的基本框架如下：
数据结构：
Queue q1, q2; //两个队列分别用于两个方向的扩展（注意在一般的广度优先算法中，只需要一个队列）
int head[2], tail[2]; //两个队列的头指针和尾指针
算法流程:
一、主控函数:
void solve()
{
1. 将起始节点放入队列q1,将目的节点放入队列q2
2. 当 两个队列都未空时，作如下循环
1) 如果队列q1里的未处理节点比q2中的少（即tail[0]-head[0] < tail[1]-head[1]),则扩展（expand()）队列q1
2) 否则扩展（expand()）队列q2 (即tail[0]-head[0] >= tail[1]-head[1]时)
3. 如果队列q1未空，循环扩展（expand()）q1直到为空
4. 如果队列q2未空，循环扩展（expand()）q2知道为空
}
二、扩展函数:
int expand(i) //其中i为队列的编号(表示q0或者q1)
{
取队列qi的头结点H
对头节点H的每一个相邻节点adj，作如下循环
1 如果adj已经在队列qi之前的某个位置出现，则抛弃节点adj
2 如果adj在队列qi中不存在[函数 isduplicate(i)]
1） 将adj放入队列qi
2) 如果adj 在队列(q(1-i))，也就是另外一个队列中出现[函数 isintersect()]
输出 找到路径
}
三、判断新节点是否在同一个队列中重复的函数
int isduplicate(i, j) //i为队列编号，j为当前节点在队列中的指针
{
遍历队列,判断是否存在【线性遍历的时间复杂度为O（N)，如果用HashTable优化，时间复杂度可以降到O(1)]
}
四、判断当前扩展出的节点是否在另外一个队列出现，也就是判断相交的函数：
int isintersect(i,j) //i为队列编号，j为当前节点在队列中的指针
{
遍历队列,判断是否存在【线性遍历的时间复杂度为O（N)，如果用HashTable优化，时间复杂度可以降到O(1)]
}
Source Code
Problem: 1077 User: 297752873
Memory: 10984K Time: 16MS
Language: C Result: Accepted
Source Code
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define QueueSize 400000
int f[8]={1,2,6,24,120,720,5040,40320};
int dir[4]={-3,3,-1,1};
int visited[1000000],ans[1000000];
int found;
struct eight
{
char str[10];//目前的状态
int k;//空格的位置
int fa;//父节点，便于输出
int fx;//从上个结点过来的方向0上，1下，2左，3右
}s[1000000],b;//所有的标志，以及存储刚开始的状态
int get(char str[]) //计算全排列哈希值
{
int i, j;
int ret = 0, cnt;
for(i = 1; i < 9; ++i)
{
cnt = 0;
for(j = 0; j < i; ++j)
if(str[j] > str[i])
cnt++;
ret += cnt*f[i-1];
}
return ret;
}
typedef struct
{
int front;
int rear;
int count;
int data[1000000];
}CirQueue;
CirQueue qs,qe;//使用队列，队列里保存的是各状态的下标
void InitQueue(CirQueue *Q)//建队
{
Q->front=Q->rear=0;
Q->count=0;
}
int QueueEmpty(CirQueue *Q)//判队是否空
{
return Q->count==0;
}
void EnQueue(CirQueue *Q,int x)//入队
{
Q->count++;
Q->data[Q->rear]=x;
Q->rear=(Q->rear+1)%QueueSize;
}
int DeQueue(CirQueue *Q)//出队，并删除队首元素
{
int temp;
temp=Q->data[Q->front];
Q->count--;
Q->front=(Q->front+1)%QueueSize;
return temp;
}
void print(int a,int b,int flag,int fx)//a是正向左边的点，b是反向右边的点，不相连 ，flag时是正向搜到的
{
int top=0;
if(flag)//正向搜索时就将要输出的那个方向放到栈里
{
ans[top++]=fx;
while(a!=s[a].fa)
{
ans[top++]=s[a].fx;
a=s[a].fa;
}
while(top--)
{
switch(ans[top])
{
case 0:printf("u");break;
case 1:printf("d");break;
case 2:printf("l");break;
case 3:printf("r");break;
default:break;
}
}
while(b!=s[b].fa)
{
switch(s[b].fx)
{
case 0:printf("d");break;
case 1:printf("u");break;
case 2:printf("r");break;
case 3:printf("l");break;
default:break;
}
b=s[b].fa;
}
}
else {//方向搜索时就将下一个方向反向直接输出
while(a!=s[a].fa)
{
ans[top++]=s[a].fx;
a=s[a].fa;
}
while(top--)
{
switch(ans[top])
{
case 0:printf("u");break;
case 1:printf("d");break;
case 2:printf("l");break;
case 3:printf("r");break;
default:break;
}
}
switch(fx)
{
case 0:printf("d---");break;
case 1:printf("u");break;
case 2:printf("r");break;
case 3:printf("l");break;
default:break;
}
while(b!=s[b].fa)
{
switch(s[b].fx)
{
case 0:printf("d");break;
case 1:printf("u");break;
case 2:printf("r");break;
case 3:printf("l");break;
default:break;
}
b=s[b].fa;
}
}
printf("
");
}
void BFS_expand(CirQueue *Q,int flag)
{
int ss=DeQueue(Q),i,x,k;//ss是队首元素
char a[10],temp;
for(i=0;i<4;i++)
{
if(i==0&&s[ss].k<3)continue;
if(i==1&&s[ss].k>=6)continue;
if(i==2&&s[ss].k%3==0)continue;
if(i==3&&s[ss].k%3==2)continue; //因为这个本应二维存储的图案，要处理好边缘问题，这里纠结了好久
k=s[ss].k+dir[i];//方向
if(k<0||k>8) continue;//如果超出范围，就找寻下个结点
strcpy(a,s[ss].str);
temp=a[k];a[k]=a[s[ss].k];a[s[ss].k]=temp; // 获取子节点的状态
x=get(a);//子节点的哈希值
if(flag) // 在正向队列中判断
{
if(visited[x]!=1)// 没在正向队列出现过
{
if(visited[x]==2) // 该状态在反向队列中出现过
{
print(ss,x,flag,i);
found=1;
return ;
}
visited[x]=1; // 标记为在在正向队列中
s[x].k=k;
s[x].fx=i;
strcpy(s[x].str,a);
s[x].fa=ss;
EnQueue(Q,x);// 入队
}
}
else // 在反向队列中判断
{
if (visited[x]!=2)// 没在反向队列出现过
{
if(visited[x]==1) // 该状态在正向队列中出现过
{
print(x,ss,flag,i);
found=1;
return ;
}
visited[x]=2; // 标记为在在反向队列中
s[x].k=k;
s[x].fx=i;
strcpy(s[x].str,a);
s[x].fa=ss;
EnQueue(Q,x);// 入队
}
}
}
}
void DBFS()//双广
{
int x=get(b.str),y=get("123456780"); //x是正向，输入的，y则是目的状态，固定的
if(strcmp(b.str,"123456780")==0)
{
printf("lr
");
found=1;
return ;
}
memset(visited,0,sizeof(visited)); // 判重数组，初始化为0
InitQueue(&qs);
InitQueue(&qe);
//======正向扩展的状态标记为1，反向扩展标记为2
visited[x]=1; // 初始状态标记为1
visited[y]=2; // 结束状态标记为2
s[x].k=b.k;strcpy(s[x].str,b.str);s[x].fa=x;
s[y].k=8;strcpy(s[y].str,"123456780");s[y].fa=y;
EnQueue(&qs,x);// 初始状态入正向队列
EnQueue(&qe,y);// 结束状态入反向队列
while(!QueueEmpty(&qs)&&!QueueEmpty(&qe))
{
if(qs.count>qe.count)//队中结点少的先行，可提高效率
BFS_expand(&qe,0); // 在正向队列中搜索
else BFS_expand(&qs,1);
if(found) // 搜索结束
return ;
}
while(QueueEmpty(&qs)==0)
{
BFS_expand(&qs,1);
if(found)return;
}
while(0==QueueEmpty(&qe))
{
BFS_expand(&qe,0);
if(found)return;
}
}
int main()
{
int i,m,j;
char a[100];
gets(a);
j=0;
for(i=0;i<strlen(a);i++)
{
if(a[i]==' ')continue;
if(a[i]=='x')
{
a[j]='0';
m=j;
j++;
}else a[j++]=a[i];
}
a[j]=' ';
strcpy(b.str,a);
b.k=m;
found=0;//标志变量初始化
//printf("m=%d %s
",b.k,b.str);
DBFS();
if(found==0)
printf("unsolvable
");
//system("pause");
return 0;
}