雙向BFS
適用于目標(biāo)節(jié)點已知的情況;初始結(jié)點向目標(biāo)結(jié)點和目標(biāo)結(jié)點向初始結(jié)點同時擴展，直至在兩個擴展方向上出現(xiàn)同一個結(jié)點炼吴，搜索結(jié)束。
雙向廣搜模版：
void TBFS()
{
if(s1.state==s2.state)//起點終點相同時要特判
{
//do something
found=true;
return;
}
bool found=false;
memset(visited,0,sizeof(visited)); // 判重數(shù)組
while(!Q1.empty()) Q1.pop(); // 正向隊列
while(!Q2.empty()) Q2.pop(); // 反向隊列
//======正向擴展的狀態(tài)標(biāo)記為1疫衩，反向擴展標(biāo)記為2
visited[s1.state]=1; // 初始狀態(tài)標(biāo)記為1
visited[s2.state]=2; // 結(jié)束狀態(tài)標(biāo)記為2
Q1.push(s1); // 初始狀態(tài)入正向隊列
Q2.push(s2); // 結(jié)束狀態(tài)入反向隊列
while(!Q1.empty() || !Q2.empty())
{
if(!Q1.empty())
BFS_expand(Q1,true); // 在正向隊列中搜索
if(found) // 搜索結(jié)束
return ;
if(!Q2.empty())
BFS_expand(Q2,false); // 在反向隊列中搜索
if(found) // 搜索結(jié)束
return ;
}
}
void BFS_expand(queue<Status> &Q,bool flag)
{
s=Q.front(); // 從隊列中得到頭結(jié)點s
Q.pop()
for( 每個s 的子節(jié)點 t )
{
t.state=Gethash(t.temp) // 獲取子節(jié)點的狀態(tài)
if(flag) // 在正向隊列中判斷
{
if (visited[t.state]!=1）// 沒在正向隊列出現(xiàn)過
｛
if(visited[t.state]==2) // 該狀態(tài)在反向隊列中出現(xiàn)過
{
各種操作硅蹦；
found=true；
return;
}
visited[t.state]=1; // 標(biāo)記為在在正向隊列中
Q.push(t); // 入隊
｝
｝
else // 在正向隊列中判斷
{
if (visited[t.state]!=2） // 沒在反向隊列出現(xiàn)過
｛
if(visited[t.state]==1) // 該狀態(tài)在正向向隊列中出現(xiàn)過
{
各種操作闷煤；
found=true童芹；
return;
}
visited[t.state]=2; // 標(biāo)記為在反向隊列中
Q.push(t); // 入隊
｝
｝
}
A - Eight 八數(shù)碼
題解:
code source
康托展開
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
#define N 10
#define MAX 365000
char visited[MAX];
int father1[MAX]; // 保存正向搜索當(dāng)前狀態(tài)的父親狀態(tài)結(jié)點
int father2[MAX]; // 保存反向搜索當(dāng)前狀態(tài)的父親狀態(tài)結(jié)點
int move1[MAX]; // 正向搜索的方向保存
int move2[MAX]; // 反向搜索的方向保存
struct Status // 結(jié)構(gòu)
{
char eight[N]; // 八數(shù)碼狀態(tài)
int space; // x 位置
int state; // hash值,用于狀態(tài)保存與判重
};
queue<Status> Q1; // 正向隊列
queue<Status> Q2; // 反向隊列
Status s,s1,s2,t;
bool found; // 搜索成功標(biāo)記
int state; // 正反搜索的相交狀態(tài)
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[]) // 康托展開(獲取狀態(tài)，用于判重)
{
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[]) // 求狀態(tài)的逆序數(shù)
{
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]); // 交換兩個數(shù)位置
t.state=Gethash(t.eight);
if(flag) // 在正向隊列中判斷
{
if(visited[t.state]!=1 && ReverseOrder(t.eight)==0) // 未在正向隊列出現(xiàn)過并且滿足奇偶性
{
move1[t.state]=i; // 保存正向搜索的方向
father1[t.state]=s.state; // 保存正向搜索當(dāng)前狀態(tài)的父親狀態(tài)結(jié)點
if(visited[t.state]==2) // 當(dāng)前狀態(tài)在反向隊列中出現(xiàn)過
{
state=t.state; // 保存正反搜索中相撞的狀態(tài)(及相交點)
found=true; // 搜索成功
return;
}
visited[t.state]=1; // 標(biāo)記為在正向隊列中
Q.push(t); // 入隊
}
}
else // 在反向隊列中判斷
{
if(visited[t.state]!=2 && ReverseOrder(t.eight)==0) // 未在反向隊列出現(xiàn)過并且滿足奇偶性
{
move2[t.state]=i; // 保存反向搜索的方向
father2[t.state]=s.state; // 保存反向搜索當(dāng)前狀態(tài)的父親狀態(tài)結(jié)點
if(visited[t.state]==1) // 當(dāng)前狀態(tài)在正向隊列中出現(xiàn)過
{
state=t.state; // 保存正反搜索中相撞的狀態(tài)(及相交點)
found=true; // 搜索成功
return;
}
visited[t.state]=2; // 標(biāo)記為在反向隊列中
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; // 初始狀態(tài)
father1[s1.state]=-1;
visited[s2.state]=2; // 目標(biāo)狀態(tài)
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[]) // 從相交狀態(tài)向初始狀態(tài)尋找路徑
{
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[]) // 從相交狀態(tài)向目標(biāo)狀態(tài)尋找路徑
{
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
題意:
解開密碼鎖鲤拿，從初始狀態(tài)到開鎖狀態(tài)問最少做幾次操作假褪。操作可以是上下轉(zhuǎn)動（上下加減1，特別的：9 + 1 = 1近顷， 1 - 0 = 9 ）和交換兩個相鄰位（最左面的和最右面的不相鄰）生音。一共8+3=11種狀態(tài)擴展
#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個相同的（彼此之間無區(qū)別）棋子，規(guī)定每個棋子可以移動到相鄰的空閑格子內(nèi)（上下左右）幕庐，也可以跨過相鄰的棋子到更遠一步的格子內(nèi)【米叮現(xiàn)在給出起始和結(jié)束時四個棋子的位置，問從開始位置能否在八步之內(nèi)移到結(jié)束位置异剥。
題解:
- 判重:
因為棋子之間無差別,所以每個棋局可以用八維數(shù)組表示int vis[8][8][8][8][8][8][8][8],先將棋局的所有四個棋子坐標(biāo)從小到大排序,再填入vis;但是所需內(nèi)存為(88)*4字節(jié)=6710萬字節(jié),肯定會溢出,這種方法是不行的;所以用map<int,int>來存訪問狀態(tài),棋局的唯一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;
}
