1eHz

用户名：dxy1397

访问量：16243

签　名：

等　　级
排　　名	1114
经　　验	3194
参赛次数	0
文章发表	15
年　　龄	0
在职情况	学生
学　　校	武汉
专　　业

　　自我简介：

TA的其他文章

✔✔✔ 树的直径问题+DFS求解 [c++]
浏览：912

你可能喜欢

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

A+B for Input-Output Practice (I) （C++代码）

优质题解

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

　　作者: 1eHz　　　　发表时间：2020-12-11 23:08:25 浏览：2648　|　评论：3　

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

![](/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分

57 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

　　评论区

早起床

不用加《string》头文件吗？为啥

2022-09-29 19:44:39

说句不好吃的

如果是死局怎么办 比如12345678. 和12345687.

2021-03-05 14:26:24

强

为什么会编译错误？

2021-02-02 11:55:07

1eHz

TA的其他文章

你可能喜欢

汽水瓶（C语言代码）

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

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

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

A+B for Input-Output Practice (I) （C++代码）

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

评论区

精彩推荐

求圆的面积（C++代码）这里推荐使用宏定义

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

C二级辅导-同因查找（C语言代码）

【绝对值排序】（C++代码）

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

C语言训练-求函数值（C语言代码）

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

C语言训练-自由落体问题（C语言代码）

简单的a+b （C语言代码）

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

1eHz

TA的其他文章

你可能喜欢

汽水瓶 （C语言代码）

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

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

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

A+B for Input-Output Practice (I) （C++代码）

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

评论区

精彩推荐

求圆的面积 （C++代码）这里推荐使用宏定义

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

C二级辅导-同因查找 （C语言代码）

【绝对值排序】 （C++代码）

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

C语言训练-求函数值 （C语言代码）

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

C语言训练-自由落体问题 （C语言代码）

简单的a+b （C语言代码）

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

汽水瓶（C语言代码）

　　评论区

求圆的面积（C++代码）这里推荐使用宏定义

C二级辅导-同因查找（C语言代码）

【绝对值排序】（C++代码）

C语言训练-求函数值（C语言代码）

C语言训练-自由落体问题（C语言代码）