目录
前言
传统bfs
双向广搜
open the lock
问题描述
输入
输出
问题分析
状态转变
去重
单向搜索的bfs
双向广搜
结束条件
输出步数
前言
其实这题数据不算复杂，不用双向广搜也可以完成，仅仅是为了更直观展现双向广搜的编码方式。
传统bfs
bfs向来都是搜索问题的一把好手，但一直以来bfs都有一个痛点，就是随着bfs层数的增加，bfs所要入队的元素一般会增长很快，有时的指数形，去重做的比较好那就是线性增长，但如果数据庞大是，这个数量依旧惊人
（线性增长） （指数增长）
双向广搜
如果我们已知起点和终点，分别从起点和终点出发，那么就可以减少大量的状态数量
总结一点，如果去重都无法减少庞大的状态数量，那么就可以考虑双向广搜
open the lock
问题描述
有一个密码锁，总共四位数字，现已知四位数字的初始状态，和开锁密码，求最少几步可以开锁，密码锁上可以进行的操作，对于密码锁上的任意一位数字，都可以加一或减一，但如果数字原先为9，加一后为1，数字原先为1，减一后为9，也可以和该数字相邻的数字交换位置，最后一位数字和第一位数字不相邻，每次操作算一步
输入
第一行输入一个整数代表有多个测试，对于每个测试每行输入两个四位数，分别代表起始数字和密码锁密码
输出
对于每个测试，输出一个整数，代表所花费的最少步数
问题分析
本题其实没有特别的难点，最主要的就是处理四位数之间状态的转变
状态转变
我使用了一个函数来封装这个转变：
string Skip(string& ss, int i, int j) {//注：字符-'0' 字符变数字，数字+'0' 数字变字符/*i：操作目标四位数的位数j：操作方法ss：目标四位数*/int m;if (j == 1) {m = ss[i] - '0' + 1;if (m == 10) m = 1;ss[i] = m + '0';}if (j == 2) {m = ss[i] - '0' - 1;if (m == 0) m = 9;ss[i] = m + '0';}if (j == 3 && i <= 2) { //j<=2，最后一位数字不交换，其实也不是说不交换，就是我们只考虑单项交换，所以最后一位数字相当于不交换，其实他还是可以和他的前一位数字交换的，只是发起交换的对象不是它Swap(ss, i);}return ss;
}值得一提的是交换操作，最后一位数字不交换，其实也不是说不交换，就是我们只考虑单项交换，所以最后一位数字相当于不交换，其实他还是可以和他的前一位数字交换的，只是发起交换的对象不是它
去重
这里我使用的是map去重，也可以用set去重，详情请看bfs与判重
单向搜索的bfs
其实本题单向搜索就可以完成了，因为判重操作后，每次进队的数量不会超过9999-1111，不算多，所以也可以通过：
#include<iostream>
#include<queue>
#include<map>
using namespace std;string st, ed;struct node {string s;int step;node(){}node(string ss,int st):s(ss),step(st){}
};node now, nxt;
queue<node>que;
map<string, bool>mp;void Swap(string& ss, int i) {char tmp = ss[i];ss[i] = ss[i + 1];ss[i + 1] = tmp;
}string Skip(string& ss,int i,int j) {int m;if (j == 1) {m = ss[i] - '0' + 1;if (m == 10) m = 1;ss[i] = m + '0';}if (j == 2) {m = ss[i] - '0' - 1;if (m == 0) m = 9;ss[i] = m + '0';}if (j == 3 && i<=2) {Swap(ss, i);}return ss;
}void bfs() {que.push(node(st, 0));mp[st] = true;while (!que.empty()) {now = que.front();que.pop();for (int i = 0; i < 4; i++) { //交换操作或数值改变操作for (int j = 1; j <= 3; j++) {nxt.s = now.s; //这个注意一下，每次修改都是在now.s的基础上该nxt.s = Skip(nxt.s, i, j);if (nxt.s == ed) {cout << nxt.s << endl;cout << now.step+1 << endl;return;}if (!mp[nxt.s]) {cout << nxt.s << endl;nxt.step = now.step + 1;que.push(node(nxt));mp[nxt.s] = true;}}}}
}int main() {int test;cin >> test;while (test--) {cin >> st;cin >> ed;//cout << st << ed;if (st == ed) {cout << 0 << endl;continue;}mp.clear();bfs();}
}双向广搜
使用双向广搜，可以减少一次进入队列的状态数量，也是个不错的算法
结束条件
单向搜索的结束条件可以根据是否到达终点判断，当时双向搜索是在中途就已经结束了，所以还需要对结束条件进行讨论
我们定义了两个map，如果找到一个位置，两个map都已经搜过，那么这个点就是相遇点，结束搜索。
输出步数
单向搜索的输出很简单，只需要输出now.step即可，但是双向搜索显然不行，因为两个now节点不一定同时指向同一个四位数，所以还需要一个dis数组保存步数
接下来就可以编写代码了（这里我使用双队列的双向广搜）
#include<iostream>
#include<queue>
#include<map>
using namespace std;string st, ed;struct node {string s;int step;node() {}node(string ss, int st) :s(ss), step(st) {}
};node nowa, nxta;
node nowb, nxtb;;
queue<node>qa; //从起点开始搜
queue<node>qb; //从终点开始搜
map<string, bool>mp1; //起点队列判重
map<string, bool>mp2; //终点队列判重
map<string, int>dis; //记录距离void Swap(string& ss, int i) {//其实交换操作可以看成是单向的，因为双向和单向结果没区别char tmp = ss[i];ss[i] = ss[i + 1];ss[i + 1] = tmp;
}string Skip(string& ss, int i, int j) {//注：字符-'0' 字符变数字，数字+'0' 数字变字符int m;if (j == 1) {m = ss[i] - '0' + 1;if (m == 10) m = 1;ss[i] = m + '0';}if (j == 2) {m = ss[i] - '0' - 1;if (m == 0) m = 9;ss[i] = m + '0';}if (j == 3 && i <= 2) { //j<=2，最后一位数字不交换，其实也不是说不交换，就是我们只考虑单项交换，所以最后一位数字相当于不交换，其实他还是可以和他的前一位数字交换的，只是发起交换的对象不是它Swap(ss, i);}return ss;
}void bfs() {qb.push(node(ed, 0));qa.push(node(st, 0));dis[st] = 0;dis[ed] = 0;mp1[st] = true;mp2[ed] = true;while (!qa.empty() && !qb.empty()) {//保证起点和终点同步扩散if (qa.size() < qb.size()) {//起点nowa = qa.front();qa.pop();for (int i = 0; i < 4; i++) { //交换操作或数值改变操作for (int j = 1; j <= 3; j++) {nxta.s = nowa.s; //这个注意一下，每次修改都是在now.s的基础上该nxta.s = Skip(nxta.s, i, j);if (mp2[nxta.s] == true) {//cout << nxta.s << endl;cout << nowa.step + dis[nxta.s]+1 << endl; //注意这里要加1，因为起点和终点的step都是0return;}if (!mp1[nxta.s]) {//cout << nxta.s << endl;nxta.step = nowa.step + 1;qa.push(node(nxta));dis[nxta.s] = nxta.step;mp1[nxta.s] =true;}}}}else {//终点nowb = qb.front();qb.pop();for (int i = 0; i < 4; i++) { //交换操作或数值改变操作for (int j = 1; j <= 3; j++) {nxtb.s = nowb.s; //这个注意一下，每次修改都是在now.s的基础上该nxtb.s = Skip(nxtb.s, i, j);if (mp1[nxtb.s]==true) {cout << nowb.step +dis[nxtb.s]+1<< endl; return;}if (!mp2[nxtb.s]) {nxtb.step = nowb.step + 1;qb.push(node(nxtb));dis[nxtb.s] = nxtb.step;mp2[nxtb.s] = true;}}}}}
}int main() {int test;cin >> test;while (test--) {cin >> st;cin >> ed;if (st == ed) {cout << 0 << endl;continue;}bfs();//很多人喜欢用数组实现，但我还是倾向于用stl，更加简洁mp1.clear();mp2.clear();dis.clear();}
}
