李华

用户名：2645479600

访问量：18652

签　名：

等　　级
排　　名	478
经　　验	4691
参赛次数	2
文章发表	22
年　　龄	22
在职情况	学生
学　　校	华软、江理
专　　业	电信、计算机

　　自我简介：

欢迎探讨

TA的其他文章

蓝桥杯剪格子-题解(C语言代码)-----初学者可以看看，详细带图（dfs）
浏览：1127

[2013年第四届真题]危险系数-题解(C++代码)------STL，dfs
浏览：921

蓝桥杯历届试题-国王的烦恼-题解(C语言 with STL)---参考啊哈算法,文字解释详细
浏览：1572

你可能喜欢

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

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

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

蓝桥杯历届试题-九宫重排-题解(C语言 with STL)---简略、详细思路都有。初学者可以看看

　　作者: 李华　　　　发表时间：2020-03-02 16:11:27 浏览：2766　|　评论：3　

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

#### 简略思路:
#### 1.每走一步其实就是与相邻的格子交换，可以转化为与空白格子下标相差（+3，-3，-1，+1）的格子交换。
不知道什么意思的话,后面会详细解释
#### 2.开一个映射map，每移动一次就将当前的情况存起来，防止重复搜索
#### 3.用广度优先搜索，搜到结束的情况就直接结束
![](/image_editor_upload/20200302032807_30852.png)

------
详细思路:
1.每走一步其实就是与相邻的格子交换，可以转化为与空白格子下标相差（+3，-3，-1，+1）的格子交换。——即上移就是与下标加三的格子交换，下移就是与下标减三的格子交换，左移右移同理。这里有一个需要注意的地方，一个格子想要左移必须保证他不在第一列，右移必须保证他不在最后一列，同理上移和下移不能超过第一行和最后一行，不能超过第一行和最后一行可以理解为下标不能在0~8之外。详见代码17行的check函数
.
2.开一个映射map，每移动一次就将当前的情况存起来，防止重复搜索。开一个<string,map>类型的映射mp，每走一步就将它存入mp。没学过map的话，可以理解为这是一个下标为字符串的标记数组，每出现一个字符串就将下标对应的元素赋值为1，表明这个字符串出现过了。可以用一个叫mp.count()的函数检查这个字符串有没有出现过。如果不用map查重，我试了一下，用string类型的vector，每移动一次前检查vector里面有没有相同的情况，这样会超时
.
3.用广度优先搜索从初始的空白格子搜，搜到结束的情况就直接结束。尽量用广搜，这玩意适合寻找最小步数，深搜容易超时。
###### 欢迎讨论，有疑问可以私信或评论
```cpp
#include <iostream>
#include <cstdio>
#include <map>
#include <string>
#include <queue>
using namespace std;
map<string,int> mp;	//用于存储某种情况是否出现过 
int change[4]={3,-3,-1,1}; 
struct node
{
	string s;
	int step;
}first;	//初始状态
queue<node> q;
int n,move_;
char temp;
string temp_s;
int check(int u, int v)	//u起点,v终点 
{
	if (v < 0 || v>8)	return 0;
	if (v == u - 1)	//如果是左移一位，必须保证起点不在第一列 
	{
		if (u == 0 || u == 3 || u == 6)	return 0;
	}
	if (v == u + 1)	//如果是右移一位,必须保证起点不在最后一列
	{
		if (u == 2 || u == 5 || u == 8)	return 0;
	}
	return 1;	//都不会违规就返回1 
}
int find_(string ss)
{
	if(mp.count(ss))	return 0;	//如果已存在 
	return 1;
}
int main()
{
	string s_first, s_last;
	cin >> s_first >> s_last;
	first.s = s_first;	//初始状态,步数为0 
	first.step = 0;
	q.push(first);	//将队首压入队列
	mp[first.s]=1;
	while (!q.empty())
	{
		node a = q.front();	//建一个新节点等于队头
		node t = a;
		q.pop();	//出队
		if (a.s == s_last)
		{
			cout << a.step;
			return 0;
		}
		for (int i = 0; i < a.s.size(); i++)	//寻找.的位置 
		{
			if (a.s[i] == '.')	n = i;
		}
		for(int i=0;i<4;i++)
		{
			if(check(n,n+change[i]))
			{
				a=t;
				move_=change[i];
				temp_s=a.s;
				temp=temp_s[n+move_];	//取出要交换的字符,交换两个格子 
				temp_s[n+move_]=temp_s[n];
				temp_s[n]=temp; 
				if(find_(temp_s))	//如果这种情况没有出现过就进行真正的交换 
				{
					temp=a.s[n+move_];
					a.s[n+move_]=a.s[n];
					a.s[n]=temp;	//交换
					a.step++;
					mp[a.s]=1;	//标记
					q.push(a);	//将a入队 
				}
			}
		}
	}
	cout << "-1";
	return 0;
}

```

0.0分

46 人评分

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

　　评论区

Miracle

编译错误？

2021-03-23 18:52:32

会吐泡泡的蓝鲸

时间超限了。。

2020-08-04 20:34:48

junmoxiao

讲的很好！！！

2020-03-24 22:46:28

李华

TA的其他文章

你可能喜欢

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

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

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

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

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

蓝桥杯历届试题-九宫重排-题解(C语言 with STL)---简略、详细思路都有。初学者可以看看

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题6.1 （C++代码）__gcd()是已经写好的函数，可以直接使用

汽水瓶（C语言代码）怎么答案错误？？？？？

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

C语言训练-素数问题（C语言代码）

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

求圆的面积（C语言代码）

DNA （C语言描述，数据结构）

三角形（C++代码）递归（存在大量重复计算，容易出现时间超限）

a+b

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

李华

TA的其他文章

你可能喜欢

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

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

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

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

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

蓝桥杯历届试题-九宫重排-题解(C语言 with STL)---简略、详细思路都有。初学者可以看看

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题6.1 （C++代码）__gcd()是已经写好的函数，可以直接使用

汽水瓶 （C语言代码）怎么答案错误？？？？？

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

C语言训练-素数问题 （C语言代码）

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

求圆的面积 （C语言代码）

DNA （C语言描述，数据结构）

三角形 （C++代码）递归（存在大量重复计算，容易出现时间超限）

a+b

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

　　评论区

汽水瓶（C语言代码）怎么答案错误？？？？？

C语言训练-素数问题（C语言代码）

求圆的面积（C语言代码）

三角形（C++代码）递归（存在大量重复计算，容易出现时间超限）