pingfan443

**思路**：使用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 人评分

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

　　评论区

风化

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

2021-04-11 20:18:26

李达

2020-09-30 13:47:14

pingfan443

TA的其他文章

你可能喜欢

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

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

C语言训练-计算1~N之间所有奇数之和（C语言代码）

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

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

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

评论区

精彩推荐

蓝桥杯历届试题-九宫重排（C++代码）

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

C语言训练-求1+2!+3!+...+N!的和（C语言代码）万恶的long long

wu-淘淘的名单（C++代码）

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

【偶数求和】（C语言代码）

1118（求助_已解决）

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

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

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

pingfan443

TA的其他文章

你可能喜欢

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

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

C语言训练-计算1~N之间所有奇数之和 （C语言代码）

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

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

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

评论区

精彩推荐

蓝桥杯历届试题-九宫重排 （C++代码）

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

C语言训练-求1+2!+3!+...+N!的和 （C语言代码）万恶的long long

wu-淘淘的名单 （C++代码）

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

【偶数求和】 （C语言代码）

1118（求助_已解决）

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

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

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

C语言训练-计算1~N之间所有奇数之和（C语言代码）

　　评论区

蓝桥杯历届试题-九宫重排（C++代码）

C语言训练-求1+2!+3!+...+N!的和（C语言代码）万恶的long long

wu-淘淘的名单（C++代码）

【偶数求和】（C语言代码）

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