七つ一旋桜

用户名：uq_44081578510

访问量：7800

签　名：

没错，我正在摸鱼~

等　　级
排　　名	3440
经　　验	1844
参赛次数	0
文章发表	21
年　　龄	0
在职情况	学生
学　　校	肥宅大学
专　　业	捡垃圾工程

　　自我简介：

你看看这只旋桜就是逊啦

TA的其他文章

旋桜-蓝桥杯2013年第四届真题-错误票据-题解(C++代码)
浏览：381

旋桜-蓝桥杯历届试题-翻硬币-题解(C++代码)
浏览：290

你可能喜欢

A+B for Input-Output Practice (V) （C语言代码）

旋桜-九宫重排-双向BFS(C++代码)

　　作者: 七つ一旋桜　　　　发表时间：2020-01-21 15:37:43 浏览：1286　|　评论：2　

原题链接：蓝桥杯历届试题-九宫重排

如果这题单纯用BFS可能会超时
于是考虑使用双向BFS
~~从终点和起点同时开始搜索，左右包抄，当然要快一点了~~
据说这题用双向BFS比单向BFS要快20倍
当然不是所有最短路径题都可以使用双向BFS
######使用双向BFS的前提是要知道起点和终点######
这个算法的大致思路是一端从起点开始搜
另一端从终点开始搜
两端边搜遍做标记
如果发现标记重合
说明已经找到了解

下面贴出我AC代码

```cpp
#include <iostream>
#include <string>
#include <map>
#include <queue>
#include <algorithm>

using namespace std;

string first, last, str1, str2;		//这里选择string类作为输出
int flag, x, y;
map<string, int>dis, vis;	//用map去重同时方便查询，dis表示开始找的点到当前点的距离
queue<string>q1, q2;		//两个队列
char m[3][3];				//九宫字符数组
const int dir[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

bool in(int x, int y){				//判断是否超出九宫
	return x >= 0 && x < 3 && y >= 0 && y < 3;
}

void toMatrix(string str){				//把字符串变成九宫字符数组
	for(int i = 0; i < str.size(); i++){	//算法实现比较简单，模拟一下即可
		m[i / 3][i % 3] = str[i];
	}
}

string toString(){					//把九宫字符数组转化为字符串
	string str;
	for(int i = 0; i < 3; i++){
		for(int j = 0; j < 3; j++){
			str.push_back(m[i][j]);		//一个一个push_back
		}
	}
	return str;
}

int dbfs(){					//重头戏来了
	q1.push(first);			//q1从起点开始找
	dis[first] = 1;			//一开始赋值1
	vis[first] = 1;			//q1访问过的赋值为1
	q2.push(last);			//q2从终点开始找
	dis[last] = 1;
	vis[last] = 2;			//q2访问过的赋值为2
	while(!q1.empty() && !q2.empty()){//如果其中一个队列为空，还没有找到解，说明无解
		if(q1.size() < q2.size()){	//根据队列的容量来判断是从哪一端找，谁少谁出列
			str1 = q1.front();
			q1.pop();
			flag = 1;				//作一下是哪一个队列出列的标记
		}
		else{
			str1 = q2.front();
			q2.pop();
			flag = 2;
		}
		toMatrix(str1);				//转化为九宫数组
		for(int i = 0; i < 3; i++){		//找小数点
			for(int j = 0; j < 3; j++){
				if(m[i][j] == '.'){
					x = i;
					y = j;
				}
			}
		}
		for(int i = 0; i < 4; i++){		//四个方向开始试探
			int tx = x + dir[i][0];
			int ty = y + dir[i][1];
			if(in(tx, ty)){
				swap(m[x][y], m[tx][ty]);		//试探
				str2 = toString(); 
				if(!dis.count(str2)){			//如果没有访问，就一下标记
					dis[str2] = dis[str1] + 1;
					vis[str2] = vis[str1];		//这样写可以避免判断是哪一端找的str2
					if(flag == 1){				//谁出的列谁就入队
						q1.push(str2);
					}else if(flag == 2){
						q2.push(str2);
					}
				}
				else{			//如果已经访问判断标记是否重合
					if(vis[str1] + vis[str2] == 3){
						int ans = dis[str1] + dis[str2] - 1;//这里记得减一
						return ans;
					}
				}
				swap(m[x][y], m[tx][ty]);		//试探完毕一定要记得要回溯
			}
		}
	}
	return -1;					//没有找到，返回-1
}

int main(){
	cin >> first >> last;
	if(first == last){
		cout << 0 << endl;
	}
	else{
		cout << dbfs() << endl;
	}
	return 0;
}
```
如果代码有什么不足之处，请指正

0.0分

19 人评分

C语言网推出会员服务，提供C/C++/算法/Python等多套视频学练课程+源码资源社群答疑+私活推荐等资源，享受丰富的技术学习到变现的乐趣，以含金量和学习效果勇敢挑战同类辅导！点击了解开通

　　评论区

boxplot

请问q每次都pop，push一次，那么这个队列长度不应该一直是1吗，怎么判断谁大谁小呀

2021-04-09 17:38:22

LilyGirl

能问一下这个dis数组是干什么用的吗？

2020-10-14 16:28:53

七つ一旋桜

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题6.4 （C语言代码）

A+B for Input-Output Practice (V) （C语言代码）

输出九九乘法表（C语言代码）

C语言程序设计教程（第三版）课后习题6.3 （C++代码）

【明明的随机数】（C语言代码）

旋桜-九宫重排-双向BFS(C++代码)

评论区

精彩推荐

汽水瓶（C语言代码）怎么答案错误？？？？？

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

点我有惊喜！你懂得！

C语言程序设计教程（第三版）课后习题7.4 （Java代码）

【回文数(二)】（C语言代码）

字符串输入输出函数（C++代码）（都当成字符串吧hhhhhhhh）

C语言程序设计教程（第三版）课后习题10.5 （C语言代码）

求圆的面积（C语言代码）

2003年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

七つ一旋桜

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题6.4 （C语言代码）

A+B for Input-Output Practice (V) （C语言代码）

输出九九乘法表 （C语言代码）

C语言程序设计教程（第三版）课后习题6.3 （C++代码）

【明明的随机数】 （C语言代码）

旋桜-九宫重排-双向BFS(C++代码)

评论区

精彩推荐

汽水瓶 （C语言代码）怎么答案错误？？？？？

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

点我有惊喜！你懂得！

C语言程序设计教程（第三版）课后习题7.4 （Java代码）

【回文数(二)】 （C语言代码）

字符串输入输出函数 （C++代码）（都当成字符串吧hhhhhhhh）

C语言程序设计教程（第三版）课后习题10.5 （C语言代码）

求圆的面积 （C语言代码）

2003年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

输出九九乘法表（C语言代码）

【明明的随机数】（C语言代码）

　　评论区

汽水瓶（C语言代码）怎么答案错误？？？？？

【回文数(二)】（C语言代码）

字符串输入输出函数（C++代码）（都当成字符串吧hhhhhhhh）

求圆的面积（C语言代码）