1eHz

用户名：dxy1397

访问量：15737

签　名：

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

　　自我简介：

TA的其他文章

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

你可能喜欢

蓝桥杯历届试题-九宫重排-题解（C++代码）双向BFS满分题解

　　作者: 1eHz　　　　发表时间：2020-08-23 17:44:00 浏览：385　|　评论：0　

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

```cpp
#include <iostream>
#include <string>
#include <queue>
#include <map>
using namespace std;
char mat[3][3];  //以二维数组形式储存矩阵
int dx[4]={0,1,0,-1}, dy[4]={-1,0,1,0};

void BFS(string Start, string End){
	queue<string> qMat;  //以字符串形式储存矩阵
	qMat.push(Start);
	qMat.push(End);
	map<string,int> mCntMat;  //记录每一个矩阵累计所用步数
	map<string,int> mVisMat;  //记录每一个矩阵当前的BFS方向
	mCntMat[Start] = 0;
	mCntMat[End] = 1;
	mVisMat[Start] = 1;
	mVisMat[End] = 2;
	
	while(!qMat.empty()){
		string sCurMat = qMat.front();  //矩阵出队
		qMat.pop();
		
		int x,y,nx,ny;
		for(int j=0;j<3;j++){
			for(int k=0;k<3;k++){
				mat[j][k] = sCurMat[j*3+k];  //字符串转矩阵
				if(mat[j][k] == '.') x=j, y=k;  //记录小数点的坐标x,y
			}
		}
		
		for(int dir=0;dir<4;dir++){  //将小数点向4个方向移动尝试形成新矩阵
			nx = x + dx[dir], ny = y + dy[dir];
			if(nx<0|| nx>2|| ny<0|| ny>2) continue;
			swap(mat[x][y], mat[nx][ny]);  //交换元素位置形成新矩阵
			
			string sSucMat = "";
			for(int j=0;j<3;j++){
				for(int k=0;k<3;k++){
					sSucMat += mat[j][k];  //新矩阵转字符串形式
				}
			}
			
			if(mVisMat[sCurMat] == mVisMat[sSucMat]){  //如果新矩阵之前出现过 且原矩阵和新矩阵的BFS方向相同
				swap(mat[x][y], mat[nx][ny]);  //还原新矩阵为原矩阵
				continue;
			}
			
			if(mVisMat[sCurMat] + mVisMat[sSucMat] == 3){  //如果新矩阵之前出现过 且原矩阵和新矩阵的BFS方向不同
				cout<<mCntMat[sCurMat]+mCntMat[sSucMat]<<endl;
				return ;
			}
			
			qMat.push(sSucMat);  //新矩阵以字符串形式入队
			mCntMat[sSucMat] = mCntMat[sCurMat] + 1;  //新矩阵步数 = 原矩阵步数 + 1
			mVisMat[sSucMat] = mVisMat[sCurMat];  //新矩阵BFS方向 = 原矩阵BFS方向
			swap(mat[x][y], mat[nx][ny]);  //还原新矩阵为原矩阵
		}
	}
}

int main(){
	string a, b;
	cin>>a>>b;
	BFS(a, b);
	return 0;
}
```
[前往我的第二篇简化题解](https://blog.dotcpp.com/a/74488 "简化题解")

0.0分

3 人评分

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

1eHz

TA的其他文章

你可能喜欢

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

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

C二级辅导-阶乘数列（C语言代码）

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

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

蓝桥杯历届试题-九宫重排-题解（C++代码）双向BFS满分题解

评论区

精彩推荐

WU-字符串比较（C++代码）

母牛的故事（C语言代码）

IP判断（C语言描述，蓝桥杯）

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

数字游戏（C++代码）

青年歌手大奖赛_评委会打分（C语言代码）

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

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

1005答案错误为什么

判定字符位置（C++代码）

1eHz

TA的其他文章

你可能喜欢

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

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

C二级辅导-阶乘数列 （C语言代码）

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

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

蓝桥杯历届试题-九宫重排-题解（C++代码） 双向BFS满分题解

评论区

精彩推荐

WU-字符串比较 （C++代码）

母牛的故事 （C语言代码）

IP判断 （C语言描述，蓝桥杯）

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

数字游戏 （C++代码）

青年歌手大奖赛_评委会打分 （C语言代码）

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

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

1005答案错误为什么

判定字符位置 （C++代码）

C二级辅导-阶乘数列（C语言代码）

蓝桥杯历届试题-九宫重排-题解（C++代码）双向BFS满分题解

　　评论区

WU-字符串比较（C++代码）

母牛的故事（C语言代码）

IP判断（C语言描述，蓝桥杯）

数字游戏（C++代码）

青年歌手大奖赛_评委会打分（C语言代码）

判定字符位置（C++代码）