✔✔✔ 双向BFS+最简题解 [c++]

2768 阅读 5 评论 0 点赞

![](/image_editor_upload/20210305102333_23065.png)
*cntMat[x]：矩阵x累计所花的步数（从起点到现在的状态累积所用的步数）
dirMat[x]：矩阵x的BFS方向（1方向或2方向）*
题解全采用字符串形式存储矩阵↓
```cpp
#include <iostream>
#include <queue>
#include <map>
using namespace std;
int dx[4] = {0, 1, 0, -1}, dy[4] = {-1, 0, 1, 0};
string nextMat(string mat, int dir){
	int dotInd = mat.find('.');
	int sucX = dotInd/3 + dx[dir], sucY = dotInd%3 + dy[dir];
	if(sucX<0|| sucY<0|| sucX>2|| sucY>2) return "null";
	swap(mat[dotInd], mat[(sucX*3)+sucY]);
	return mat;
}
int BFS(string start, string end){
	queue<string> queMat;
	queMat.push(start), queMat.push(end);
	map<string, int> cntMat, dirMat;
	cntMat[start] = 0, cntMat[end] = 0;
	dirMat[start] = 1, dirMat[end] = 2;

while(!queMat.empty()){
		string curMat = queMat.front();
		queMat.pop();
		for(int i=0; i<4; i++){
			string sucMat = nextMat(curMat, i);
			if(sucMat != "null"&& dirMat[sucMat] != dirMat[curMat]){ //矩阵sucMat可行 且 矩阵sucMat在该方向上未被访过。
				if(dirMat[curMat] + dirMat[sucMat] == 3) return cntMat[curMat] + cntMat[sucMat] + 1;
				queMat.push(sucMat);
				dirMat[sucMat] = dirMat[curMat];
				cntMat[sucMat] = cntMat[curMat] + 1;
			}
		}
	}
}
int main(){
	string a, b;
	cin>>a>>b;
	cout<<BFS(a, b);
	return 0;
}
```

0.0分

9 人评分

本文分类：题解列表
浏览次数：2768 次浏览
发布日期：2020-12-11 23:08:25
本文链接：https://blog.dotcpp.com/a/74488

上一篇 > printf基础练习2-题解（C语言代码）
下一篇 > [编程入门]有规律的数列求和-题解（Python代码）

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：

一点编程也不会写的：零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码？手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

✔✔✔ 双向BFS+最简题解 [c++]

评论列表共有 5 条评论

发表评论取消回复

✔✔✔ 双向BFS+最简题解 [c++]

数位dp#2491: 信息学奥赛一本通T1587-Windy 数(C++)

点进来你会后悔的

简简单单的循环

简单的回文数

评论列表 共有 5 条评论

发表评论 取消回复

评论列表共有 5 条评论

发表评论取消回复