1eHz

用户名：dxy1397

访问量：16243

签　名：

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

　　自我简介：

TA的其他文章

✔✔✔DFS记忆化搜索[C++]
浏览：338

✔✔✔蛇形矩阵16行满分题解[C++]
浏览：3761

✔✔✔13行K-进制数满分题解[C++]
浏览：1625

你可能喜欢

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

　　作者: 1eHz　　　　发表时间：2020-08-23 17:44:00 浏览：406　|　评论：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的其他文章

你可能喜欢

IP判断（C语言代码）

C二级辅导-等差数列（C++代码）

你的开发任务（C++代码）写到一半，等有心情回来补全

点我有惊喜！你懂得！

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

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

评论区

精彩推荐

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

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

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

众数问题（C语言代码）

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

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

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

【魔板】（C++代码）

众数问题（C语言代码）

整数分类问题为什么输出总是数字8啊

1eHz

TA的其他文章

你可能喜欢

IP判断 （C语言代码）

C二级辅导-等差数列 （C++代码）

你的开发任务 （C++代码）写到一半，等有心情回来补全

点我有惊喜！你懂得！

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

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

评论区

精彩推荐

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

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

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

众数问题 （C语言代码）

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

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

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

【魔板】 （C++代码）

众数问题 （C语言代码）

整数分类问题 为什么输出总是数字8啊

IP判断（C语言代码）

C二级辅导-等差数列（C++代码）

你的开发任务（C++代码）写到一半，等有心情回来补全

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

　　评论区

众数问题（C语言代码）

【魔板】（C++代码）

众数问题（C语言代码）

整数分类问题为什么输出总是数字8啊