李华

用户名：2645479600

访问量：17679

签　名：

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

　　自我简介：

欢迎探讨

TA的其他文章

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

蓝桥杯2013年第四届真题-带分数-题解(C语言代码) ------------纯C语言,思路非常简单
浏览：1131

蓝桥杯2017年第八届真题-合根植物-题解(C语言代码)-----C语言
浏览：338

你可能喜欢

C语言程序设计教程（第三版）课后习题6.9 （C++代码）论pow函数的应用

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

　　作者: 李华　　　　发表时间：2020-03-02 16:11:27 浏览：2688　|　评论：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分

45 人评分

看不懂代码？想转换其他语言的代码？或者想问其他问题？试试问问AI编程助手，随时响应你的问题：

编程语言转换

万能编程问答

代码解释器

　　评论区

Miracle

编译错误？

2021-03-23 18:52:32

会吐泡泡的蓝鲸

时间超限了。。

2020-08-04 20:34:48

junmoxiao

讲的很好！！！

2020-03-24 22:46:28

李华

TA的其他文章

你可能喜欢

小九九（C语言代码）

C语言程序设计教程（第三版）课后习题6.9 （C++代码）论pow函数的应用

点我有惊喜！你懂得！

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

分糖果（C++代码）

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

评论区

精彩推荐

printf基础练习2 （C语言代码）

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

校门外的树（C语言代码）

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

WU-C语言程序设计教程（第三版）课后习题11.11 （C++代码）（想学链表的可以看看）

哥德巴赫曾猜测（C语言代码）

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

【亲和数】（C语言代码）

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

剪刀石头布（C语言代码）

李华

TA的其他文章

你可能喜欢

小九九 （C语言代码）

C语言程序设计教程（第三版）课后习题6.9 （C++代码）论pow函数的应用

点我有惊喜！你懂得！

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

分糖果 （C++代码）

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

评论区

精彩推荐

printf基础练习2 （C语言代码）

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

校门外的树 （C语言代码）

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

WU-C语言程序设计教程（第三版）课后习题11.11 （C++代码）（想学链表的可以看看）

哥德巴赫曾猜测 （C语言代码）

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

【亲和数】 （C语言代码）

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

剪刀石头布 （C语言代码）

小九九（C语言代码）

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

分糖果（C++代码）

　　评论区

校门外的树（C语言代码）

哥德巴赫曾猜测（C语言代码）

【亲和数】（C语言代码）

剪刀石头布（C语言代码）