1eHz

用户名：dxy1397

访问量：15620

签　名：

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

　　自我简介：

TA的其他文章

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

你可能喜欢

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

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

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

　　作者: 1eHz　　　　发表时间：2020-12-11 23:08:25 浏览：2610　|　评论：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语言代码）

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

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

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

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

评论区

精彩推荐

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

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

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

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

核桃的数量（C语言代码）

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

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

循环入门练习6 （C语言代码）

格式化数据输出（C语言代码）

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

1eHz

TA的其他文章

你可能喜欢

【数组的距离】 （C语言代码）

【作业调度方案】 （C语言代码）

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

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

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

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

评论区

精彩推荐

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

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

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

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

核桃的数量 （C语言代码）

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

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

循环入门练习6 （C语言代码）

格式化数据输出 （C语言代码）

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

【数组的距离】（C语言代码）

【作业调度方案】（C语言代码）

　　评论区

核桃的数量（C语言代码）

格式化数据输出（C语言代码）