pingfan443

用户名：liu971294083

访问量：30212

签　名：

楼上的别敲了，我跟不上

等　　级
排　　名	135
经　　验	7341
参赛次数	6
文章发表	51
年　　龄	21
在职情况	学生
学　　校	b站
专　　业	软件开发

　　自我简介：

搁劲学

TA的其他文章

蓝桥杯算法训练VIP-和为T-题解(C++代码)
浏览：356

蓝桥杯2013年第四届真题-剪格子-题解(C++代码)
浏览：186

蓝桥杯2014年第五届真题-地宫取宝-题解(C++代码)
浏览：404

你可能喜欢

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

蓝桥杯历届试题-九宫重排-题解(C++代码)

　　作者: pingfan443　　　　发表时间：2020-01-27 18:54:45 浏览：1386　|　评论：2　

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

**思路**：使用bfs+set判重（方法多种）这是最简单的。
用结构体保存初末状态步数，并且入队，向四个方向寻找下一个状态放到set集合（判重）和队列（bfs）中，一直找下去，直到找到末状态.
待更：单向bfs+set判重（7.72秒）
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef struct node {
	char origin[10];
	int step;
}node;
char last[10];
int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
queue<node>p;
set<string>vis;
void bfs()
{
	while(!p.empty())
	{
		node head=p.front();
		p.pop();
		if(!strcmp(head.origin,last))
		{
			printf("%d\n",head.step);
			return;
		}
		int pos;
		for(int i=0;head.origin[i]!='\0';i++)
		if(head.origin[i]=='.')
		{
		 	pos=i;
			break;
		}
		int x1=pos/3;
		int y1=pos%3;
		for(int i=0;i<4;i++)
		{
			int x2=x1+dir[i][0];
			int y2=y1+dir[i][1];
			if(x2>=0&&x2<3&&y2>=0&&y2<3)
			{
				node t=head;
				int pos1=x2*3+y2;
				swap(t.origin[pos],t.origin[pos1]);
				if(!vis.count(t.origin))
				{
					vis.insert(t.origin);
					t.step++;
					p.push(t);
				}
			}
		}
	}
	printf("-1\n");
}
int main()
{
	node t;
	scanf("%s%s",t.origin,last);
	t.step=0;
	p.push(t);
	vis.insert(t.origin);
	bfs();
	return 0;
 }

```
方法2：双向bfs+map判重（221ms比上一个快34倍）
```cpp
#include<bits/stdc++.h>
using namespace std;
int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
map<string,int>vis;
map<string,int>step;
string origin,last;
void bfs()
{
	if(origin==last)
	{
		printf("0\n");
		return;
	}
	queue<string>p;
	p.push(origin);
	p.push(last); 
	while(!p.empty())
	{
		string head=p.front();
		p.pop();
		int pos;
		for(int i=0;i<head.length();i++)
		if(head[i]=='.')
		{
			pos=i;
			break;
		}
		int x=pos/3;
		int y=pos%3;
		for(int i=0;i<4;i++)
		{
			int x2=x+dir[i][0];
			int y2=y+dir[i][1];
			if(x2>=0&&x2<3&&y2>=0&&y2<3)
			{
				int pos1=x2*3+y2;
				string t=head;
				swap(t[pos],t[pos1]);
				if(!vis.count(t))
				{
					vis[t]=vis[head];
					step[t]=step[head]+1;
					p.push(t);
				}
				else if(vis[head]+vis[t]==3)
				{
					printf("%d\n",step[head]+step[t]+1);
					return ;
				}
			}
		}
	}
	printf("-1\n");
}
int main()
{

cin>>origin>>last;
	vis[origin]=1;//标记除终点以外状态都是1 
	vis[last]=2;//终点状态2 
	step[origin]=0;//步数 
	bfs();
	return 0;
 }

```
总结：两种方法的比较第二个更好，时间是从洛谷的八数码难题上测出来的，这道题和那道题本质上差不多，紫书199也有详解，当然还有更好的算法，有看到最优解是0ms，膜拜~~~

0.0分

10 人评分

C语言网推出会员服务，提供C/C++/算法/Python等多套视频学练课程+源码资源社群答疑+私活推荐等资源，享受丰富的技术学习到变现的乐趣，以含金量和学习效果勇敢挑战同类辅导！点击了解开通

　　评论区

风化

为什么要将last也推入队列里呢，一开始的时候

2021-04-11 20:18:26

李达

2020-09-30 13:47:14

pingfan443

TA的其他文章

你可能喜欢

C语言考试练习题_一元二次方程（C语言代码）

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

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

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

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

蓝桥杯历届试题-九宫重排-题解(C++代码)

评论区

精彩推荐

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

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

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

C语言考试练习题_保留字母（C语言代码）

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

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

IP判断（C语言代码）

敲七（C++代码）

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

盐水的故事（C语言代码）

pingfan443

TA的其他文章

你可能喜欢

C语言考试练习题_一元二次方程 （C语言代码）

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

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

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

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

蓝桥杯历届试题-九宫重排-题解(C++代码)

评论区

精彩推荐

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

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

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

C语言考试练习题_保留字母 （C语言代码）

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

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

IP判断 （C语言代码）

敲七 （C++代码）

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

盐水的故事 （C语言代码）

C语言考试练习题_一元二次方程（C语言代码）

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

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

　　评论区

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

C语言考试练习题_保留字母（C语言代码）

IP判断（C语言代码）

敲七（C++代码）

盐水的故事（C语言代码）