双向BFS
适用于目标节点已知的情况;初始结点向目标结点和目标结点向初始结点同时扩展，直至在两个扩展方向上出现同一个结点，搜索结束。
双向广搜模版：
void TBFS()
{
if(s1.state==s2.state)//起点终点相同时要特判
{
//do something
found=true;
return;
}
bool found=false;
memset(visited,0,sizeof(visited)); // 判重数组
while(!Q1.empty()) Q1.pop(); // 正向队列
while(!Q2.empty()) Q2.pop(); // 反向队列
//======正向扩展的状态标记为1，反向扩展标记为2
visited[s1.state]=1; // 初始状态标记为1
visited[s2.state]=2; // 结束状态标记为2
Q1.push(s1); // 初始状态入正向队列
Q2.push(s2); // 结束状态入反向队列
while(!Q1.empty() || !Q2.empty())
{
if(!Q1.empty())
BFS_expand(Q1,true); // 在正向队列中搜索
if(found) // 搜索结束
return ;
if(!Q2.empty())
BFS_expand(Q2,false); // 在反向队列中搜索
if(found) // 搜索结束
return ;
}
}
void BFS_expand(queue<Status> &Q,bool flag)
{
s=Q.front(); // 从队列中得到头结点s
Q.pop()
for( 每个s 的子节点 t )
{
t.state=Gethash(t.temp) // 获取子节点的状态
if(flag) // 在正向队列中判断
{
if (visited[t.state]!=1）// 没在正向队列出现过
｛
if(visited[t.state]==2) // 该状态在反向队列中出现过
{
各种操作；
found=true；
return;
}
visited[t.state]=1; // 标记为在在正向队列中
Q.push(t); // 入队
｝
｝
else // 在正向队列中判断
{
if (visited[t.state]!=2） // 没在反向队列出现过
｛
if(visited[t.state]==1) // 该状态在正向向队列中出现过
{
各种操作；
found=true；
return;
}
visited[t.state]=2; // 标记为在反向队列中
Q.push(t); // 入队
｝
｝
}
A - Eight 八数码
题解:
code source
康托展开
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
#define N 10
#define MAX 365000
char visited[MAX];
int father1[MAX]; // 保存正向搜索当前状态的父亲状态结点
int father2[MAX]; // 保存反向搜索当前状态的父亲状态结点
int move1[MAX]; // 正向搜索的方向保存
int move2[MAX]; // 反向搜索的方向保存
struct Status // 结构
{
char eight[N]; // 八数码状态
int space; // x 位置
int state; // hash值,用于状态保存与判重
};
queue<Status> Q1; // 正向队列
queue<Status> Q2; // 反向队列
Status s,s1,s2,t;
bool found; // 搜索成功标记
int state; // 正反搜索的相交状态
int factory[]={1,1,2,6,24,120,720,5040,40320,362880}; // 0..n的阶乘
int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
int Gethash(char eight[]) // 康托展开(获取状态，用于判重)
{
int k=0;
for(int i=0;i<9;i++)
{
int t=0;
for(int j=i+1;j<9;j++)
if(eight[j]<eight[i])
t++;
k+=(t*factory[9-i-1]);
}
return k;
}
int ReverseOrder(char eight[]) // 求状态的逆序数
{
int i,j,num=0;
for(i=0;i<9;i++)
{
for(j=0;j<i;j++)
{
if(int(eight[i])==9)
{
break;
}
if(int(eight[j])==9)
continue;
if(int(eight[j])>int(eight[i]))
num++;
}
}
num=num%2;
return num;
}
void BFS_expand(queue<Status> &Q,bool flag) // 单向广度搜索
{
int k,x,y;
s=Q.front();
Q.pop();
k=s.space;
x=k/3;
y=k%3;
for(int i=0;i<4;i++)
{
int xx=x+dir[i][0];
int yy=y+dir[i][1];
if(xx>=0 && xx<=2 && yy>=0 && yy<=2)
{
t=s;
t.space=xx*3+yy; // 计算x位置
swap(t.eight[k],t.eight[t.space]); // 交换两个数位置
t.state=Gethash(t.eight);
if(flag) // 在正向队列中判断
{
if(visited[t.state]!=1 && ReverseOrder(t.eight)==0) // 未在正向队列出现过并且满足奇偶性
{
move1[t.state]=i; // 保存正向搜索的方向
father1[t.state]=s.state; // 保存正向搜索当前状态的父亲状态结点
if(visited[t.state]==2) // 当前状态在反向队列中出现过
{
state=t.state; // 保存正反搜索中相撞的状态(及相交点)
found=true; // 搜索成功
return;
}
visited[t.state]=1; // 标记为在正向队列中
Q.push(t); // 入队
}
}
else // 在反向队列中判断
{
if(visited[t.state]!=2 && ReverseOrder(t.eight)==0) // 未在反向队列出现过并且满足奇偶性
{
move2[t.state]=i; // 保存反向搜索的方向
father2[t.state]=s.state; // 保存反向搜索当前状态的父亲状态结点
if(visited[t.state]==1) // 当前状态在正向队列中出现过
{
state=t.state; // 保存正反搜索中相撞的状态(及相交点)
found=true; // 搜索成功
return;
}
visited[t.state]=2; // 标记为在反向队列中
Q.push(t); // 入队
}
}
}
}
return ;
}
void TBFS() // 双向搜索
{
memset(visited,0,sizeof(visited));
while(!Q1.empty())
Q1.pop();
while(!Q2.empty())
Q2.pop();
visited[s1.state]=1; // 初始状态
father1[s1.state]=-1;
visited[s2.state]=2; // 目标状态
father2[s2.state]=-1;
Q1.push(s1);
Q2.push(s2);
while(!Q1.empty() || !Q2.empty())
{
if(!Q1.empty())
BFS_expand(Q1,true);
if(found)
return ;
if(!Q2.empty())
BFS_expand(Q2,false);
if(found)
return ;
}
}
void PrintPath1(int father[],int move[]) // 从相交状态向初始状态寻找路径
{
int n,u;
char path[1000];
n=1;
path[0]=move[state];
u=father[state];
while(father[u]!=-1)
{
path[n]=move[u];
n++;
u=father[u];
}
for(int i=n-1;i>=0;--i)
{
if(path[i] == 0)
printf("u");
else if(path[i] == 1)
printf("d");
else if(path[i] == 2)
printf("l");
else
printf("r");
}
}
void PrintPath2(int father[],int move[]) // 从相交状态向目标状态寻找路径
{
int n,u;
char path[1000];
n=1;
path[0]=move[state];
u=father[state];
while(father[u]!=-1)
{
path[n]=move[u];
n++;
u=father[u];
}
for(int i=0;i<=n-1;i++)
{
if(path[i] == 0)
printf("d");
else if(path[i] == 1)
printf("u");
else if(path[i] == 2)
printf("r");
else
printf("l");
}
}
int main()
{
int i;
char c;
while(scanf(" %c",&c)!=EOF)
{
if(c=='x')
{
s1.eight[0]=9;
s1.space=0;
}
else
s1.eight[0]=c-'0';
for(i=1;i<9;i++)
{
scanf(" %c",&c);
if(c=='x')
{
s1.eight[i]=9;
s1.space=i;
}
else
s1.eight[i]=c-'0';
}
s1.state=Gethash(s1.eight);
for(int i=0;i<9;i++)
s2.eight[i]=i+1;
s2.space=8;
s2.state=Gethash(s2.eight);
if(ReverseOrder(s1.eight)==1)
{
cout<<"unsolvable"<<endl;
continue;
}
found=false;
TBFS();
if(found) // 搜索成功
{
PrintPath1(father1,move1);
PrintPath2(father2,move2);
}
else
cout<<"unsolvable"<<endl;
cout<<endl;
}
return 0;
}
B - Open the Lock
题意:
解开密码锁，从初始状态到开锁状态问最少做几次操作。操作可以是上下转动（上下加减1，特别的：9 + 1 = 1， 1 - 0 = 9 ）和交换两个相邻位（最左面的和最右面的不相邻）。一共8+3=11种状态扩展
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
const int MAXN=10010;
int vis[MAXN];
int step[MAXN];
struct Node
{
int num[5];
int status;
}st,ed;
int flag;
int minStep;
int toInt(int num[])
{
return num[0]*1000+num[1]*100+num[2]*10+num[3];
}
void toArray(int num,int arr[])
{
arr[0]=num/1000;
arr[1]=(num%1000)/100;
arr[2]=(num%100)/10;
arr[3]=num%10;
}
void BFS_expand(queue<Node> & que,int choose)
{
Node curr=que.front(),next;
que.pop();
for(int i=0;i<4;i++)
{
for(int j=0;j<2;j++)
{
next=curr;
if(j==0)
{
next.num[i]=curr.num[i]+1;
if(next.num[i]==10) next.num[i]=1;
}
else
{
next.num[i]=curr.num[i]-1;
if(next.num[i]==0) next.num[i]=9;
}
next.status=toInt(next.num);
int dis=step[curr.status]+1;
if(choose==0)
{
if(vis[next.status]!=1)
{
if(vis[next.status]==2)
{
flag=true;
minStep=step[next.status]+dis;
return;
}
step[next.status]=dis;
vis[next.status]=1;
que.push(next);
}
}
else
{
if(vis[next.status]!=2)
{
if(vis[next.status]==1)
{
flag=true;
minStep=step[next.status]+dis;
return;
}
step[next.status]=dis;
vis[next.status]=2;
que.push(next);
}
}
}
}
for(int i=0;i<3;i++)
{
next=curr;
next.num[i]=curr.num[i+1];
next.num[i+1]=curr.num[i];
next.status=toInt(next.num);
int dis=step[curr.status]+1;
if(choose==0)
{
if(vis[next.status]!=1)
{
if(vis[next.status]==2)
{
minStep=dis+step[next.status];
flag=true;
return;
}
vis[next.status]=1;
step[next.status]=dis;
que.push(next);
}
}
else
{
if(vis[next.status]!=2)
{
if(vis[next.status]==1)
{
minStep=dis+step[next.status];
flag=true;
return;
}
vis[next.status]=2;
step[next.status]=dis;
que.push(next);
}
}
}
}
void TBFS()
{
if(st.status==ed.status)//起点终点相同时要特判
{
minStep=0;
return;
}
queue<Node> q1;
queue<Node> q2;
q1.push(st);
q2.push(ed);
memset(vis,0,sizeof(vis));
vis[st.status]=1;
vis[ed.status]=2;
step[st.status]=0;
step[ed.status]=0;
flag=false;
while(!q1.empty()||!q2.empty())
{
if(!q1.empty())
{
BFS_expand(q1,0);
}
if(flag) return;
if(!q2.empty())
{
BFS_expand(q2,1);
}
if(flag) return;
}
}
int main()
{
int t,s1,s2;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&s1,&s2);
toArray(s1,st.num);
st.status=s1;
toArray(s2,ed.num);
ed.status=s2;
TBFS();
printf("%d\n",minStep);
}
return 0;
}
C - Solitaire
题意:
8*8的棋盘上有4个相同的（彼此之间无区别）棋子，规定每个棋子可以移动到相邻的空闲格子内（上下左右），也可以跨过相邻的棋子到更远一步的格子内。现在给出起始和结束时四个棋子的位置，问从开始位置能否在八步之内移到结束位置。
题解:
- 判重:
因为棋子之间无差别,所以每个棋局可以用八维数组表示int vis[8][8][8][8][8][8][8][8],先将棋局的所有四个棋子坐标从小到大排序,再填入vis;但是所需内存为(88)*4字节=6710万字节,肯定会溢出,这种方法是不行的;所以用map<int,int>来存访问状态,棋局的唯一id=point[0]*80+point[1]*81......+point[7]*87
#include<cstdio>
#include<queue>
#include<algorithm>
#include<map>
#include<iterator>
using namespace std;
int dir[4][2] = { {1, 0}, {0, 1}, {-1, 0}, {0, -1}};
struct Point
{
int x,y;
bool operator<(const Point &t)const
{
return x!=t.x?x<t.x:y<t.y;
}
};
struct Node
{
Point points[4];
int step;
}st,ed;
bool cmp(Point n1,Point n2){
return n1.x!=n2.x?n1.x<n2.x:n1.y<n2.y;
}
int getHash(Point *arr)
{
sort(arr,arr+4,cmp);
int sum=0;
int base=1;
for(int i=0;i<4;i++)
{
sum+=base*arr[i].x;
base*=8;
sum+=base*arr[i].y;
base*=8;
}
return sum;
}
bool BFS()
{
int hash_1=getHash(st.points);
int hash_2=getHash(ed.points);
if(hash_1==hash_2) return true;
st.step=0;
ed.step=0;
queue<Node> q1;
queue<Node> q2;
q1.push(st);
q2.push(ed);
map<int,int> vis;
vis[hash_1]=1;
vis[hash_2]=2;
while(!q1.empty()||!q2.empty())
{
if(!q1.empty())
{
Node curr=q1.front(),next;
q1.pop();
if(curr.step>=4) continue;//这里不可以写成if(curr.step>=4) return false;
for(int i=0;i<4;i++)
{
for(int j=0;j<4;j++)
{
next=curr;
next.step=curr.step+1;
next.points[i].x=curr.points[i].x+dir[j][0];
next.points[i].y=curr.points[i].y+dir[j][1];
int flag=false,flag2=false;//flag,flag2用来判断是否可以放在原来已有棋子的地方
for(int k=0;k<4;k++)
{
if((next.points[i].x==curr.points[k].x)&&(next.points[i].y==curr.points[k].y))
{
next.points[i].x=curr.points[k].x+dir[j][0];
next.points[i].y=curr.points[k].y+dir[j][1];
flag=true;
break;
}
}
if(flag)
{
for(int k=0;k<4;k++)
{
if((next.points[i].x==curr.points[k].x)&&(next.points[i].y==curr.points[k].y))
{
flag2=true;
break;
}
}
if(flag2) continue;
}
if(next.points[i].x<1||next.points[i].x>8||next.points[i].y<1||next.points[i].y>8) continue;
int index=getHash(next.points);
map<int,int>::iterator it=vis.find(index);
if(it==vis.end())
{
vis[index]=1;
q1.push(next);
}
else if((*it).second==1) continue;
else
{
return true;
}
}
}
}
if(!q2.empty())
{
Node curr=q2.front(),next;
q2.pop();
if(curr.step>=4) continue;//这里不可以写成if(curr.step>=4) return false;
for(int i=0;i<4;i++)
{
for(int j=0;j<4;j++)
{
next=curr;
next.points[i].x=curr.points[i].x+dir[j][0];
next.points[i].y=curr.points[i].y+dir[j][1];
next.step=curr.step+1;
int flag=false,flag2=false;
for(int k=0;k<4;k++)
{
if(next.points[i].x==curr.points[k].x&&next.points[i].y==curr.points[k].y)
{
next.points[i].x=curr.points[k].x+dir[j][0];
next.points[i].y=curr.points[k].y+dir[j][1];
flag=true;
break;
}
}
if(flag)
{
for(int k=0;k<4;k++)
{
if(next.points[i].x==curr.points[k].x&&next.points[i].y==curr.points[k].y)
{
flag2=true;
break;
}
}
if(flag2) continue;
}
if(next.points[i].x<1||next.points[i].x>8||next.points[i].y<1||next.points[i].y>8) continue;
int index=getHash(next.points);
map<int,int>::iterator it=vis.find(index);
if(it==vis.end())
{
vis[index]=2;
q2.push(next);
}
else if((*it).second==2) continue;
else
{
return true;
}
}
}
}
}
return false;
}
int main()
{
while(scanf("%d%d",&st.points[0].x,&st.points[0].y)!=EOF)
{
for(int i=1;i<4;i++)
{
scanf("%d%d",&st.points[i].x,&st.points[i].y);
}
for(int i=0;i<4;i++)
{
scanf("%d%d",&ed.points[i].x,&ed.points[i].y);
}
if(BFS()) printf("YES\n");
else printf("NO\n");
}
return 0;
}
