八数码与双向广搜

八数码问题：

将圆圈->直线

将8只蚱蜢跳跃->1只空盘跳跃

起始状态：012345678

终止状态：087654321

当前状态->下一状态：

(1)找到当前状态 空盘位置pos

(2)下一状态 位置tx=pos+nxt[i]

(3)下一字符串=当前字符串+交换字符(cstr[pos],cstr[tx])位置

代码：

起点的step设为1，最后答案需要减1

struct node{string s;//当前字符串int stp;//步数
};
int n;
int nxt[4]={1,2,-1,-2};
string a,b;void bfs()
{queue<node> q;map<string,int> mp;string cstr,tstr;//cstr当前字符串 tstr下一个字符串 int pos,tx;//当前0的位置 下一个数的位置cstr=a;//a入队 q.push({cstr,1});mp[cstr]=1;if(a==b){cout<<0;return ;}while(!q.empty()){auto head=q.front();q.pop();cstr=head.s;for(pos=0;pos<n;++pos){//找到cstr 0的位置 if(cstr[pos]=='0') break;}for(int i=0;i<4;++i){tx=(pos+nxt[i]+n)%n; //找到下一状态 字符位置 tstr=cstr; //得到下一字符串 tstr[pos]=cstr[tx];tstr[tx]=cstr[pos];if(mp[tstr]==0){//如果没搜过 加入队列 q.push({tstr,head.stp+1});mp[tstr]=1;	if(tstr==b){cout<<head.stp+1-1;return ;}}}}
} int main()
{n=9;a="012345678";b="087654321";bfs();return 0;
} 

双向广搜：

两个方向一起进行BFS

使用条件：

无向图(保证start->end的距离=end->start的距离)

核心：

1. 设起点是a，终点是b，从a开始正向BFS，从b开始逆向BFS，当a和b搜到同一点(状态)时，终止
2. 两个搜索并不是同时进行，而是当前状态下，哪一个搜索的队列中所含元素少，就扩展这一队列
3. 每次扩展，只扩一层

结构：

bfs函数+extend函数

代码：

用map判重，同时也记录step

为了保持代码的一致性，这里保留了struct node结构体，实际上可以去除

struct node{string s;int stp;
};
int n,nxt[4]={1,2,-1,-2};
string a,b;
bool flag;//是否相遇 void extend(queue<node> &q,map<string,int> &m1,map<string,int> &m2)
{int pos,tx;string cstr,tstr;auto head=q.front();//队首出队 q.pop();cstr=head.s;if(m2[cstr]!=0){flag=true;cout<<m1[cstr]+m2[cstr]-2;return ;}for(pos=0;pos<n;++pos){//找到队首cstr 0的位置 if(cstr[pos]=='0') break;}for(int i=0;i<4;++i){tx=(pos+nxt[i]+n)%n;//找到下一状态 字符位置 tstr=cstr;//得到下一字符串 tstr[pos]=cstr[tx];tstr[tx]=cstr[pos];if(m1[tstr]==0){//如果没搜过 加入队列 q.push({tstr,head.stp+1});m1[tstr]=m1[cstr]+1;}if(m2[tstr]!=0){//如果另一方向搜过 相遇 flag=true;cout<<m1[tstr]+m2[tstr]-2;return ;}}}void bfs()
{queue<node> q1,q2;map<string,int> mp1,mp2;q1.push({a,0});	q2.push({b,0});mp1[a]=1; mp2[b]=1;while(!q1.empty()&&!q2.empty()){//先扩展队列小的 if(q1.size()<=q2.size()) extend(q1,mp1,mp2);else extend(q2,mp2,mp1);if(flag) break;}
} int main()
{n=9;a="012345678";b="087654321";flag=false;bfs();return 0;
}