顾亦倾

##### bfs来搜索目标局面，一旦搜到一定是最小移动次数
#####任务：
	目标检查
	判重
##### 通常利用哈希表记录每一种不同的局面
```cpp
typedef int State[9];//哈希映射 
State st[Maxsize],goal;//st二维数组存储每种情形，goal数组存储目标数组 
int hash(State& s)
{
	int v = 0;
	for(int i=0; i<9; i++) v = v*10 + s[i]; //把9个数字组合成9位数 
	return 	v % Maxsize; //确保hash函数值是不超过hash表的大小的非负整数 
 
}
```
##### 复习一下三个函数
```cpp
memcpy(&t ,&s ,sizeof(s));//从源source所指的内存地址的起始位置开始拷贝n个字节到目标destin所指的内存地址的起始位置中。

if(memcmp(st[s], st[u], sizeof(st[s]))==0) return 0; //把存储区str1和存储区str2的前n个字节进行比较

memset(head, 0, sizeof(head));//为新申请的内存做初始化工作。
```
##### 插入链表的实现
```cpp
int try_to_insert(int s)
{
	int h = hash(st[s]); 
	int u = head[h]; //从表头开始查找链表 
	while(u){//把存储区str1和存储区str2的前n个字节进行比较
		if(memcmp(st[s], st[u], sizeof(st[s]))==0) return 0; //有重复，插入失败 
		u = next[u]; //顺着链表继续找 
	}
	next[s] = head[h]; //该结点插入到链表中 
	head[h] = s;
	return 1;
}
```
##### 核心bfs实现
```cpp
int bfs()
{
	init_table();
	int front=1,rear=2;
	while(front<rear)
	{
		State &s=st[front];int z;
		if(memcmp(goal,s,sizeof(s))==0) return front;
		for(int i=0;i<9;i++)
		{
			if(!s[i]) z=i;
		}
		int x=z/3,y=z%3;
		for(int i=0;i<4;i++)
		{
			int newx=x+dx[i];
			int newy=y+dy[i];
			int newz=3*newx+newy;
			if(newx<3&&newx>=0&&newy<3&&newy>=0)
			{
				State &t=st[rear];
				memcpy(&t,&s,sizeof(s));
				t[newz]=s[z];
				t[z]=s[newz];
				dist[rear]=dist[front]+1;
				if(try_to_insert(rear)) rear++;
			}
		}
		front++;
	}
	return 0;
}
```
###完整参考代码
```cpp
#include<iostream>
#include<cstring>
using namespace std;
const int Maxsize=1000000;
string str1,str2;
int dist[Maxsize];
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
typedef int State[9];
State st[Maxsize],goal;
int head[Maxsize],next1[Maxsize];
void init_table()
{
	memset(head,0,sizeof(head));
}
int hash1(State &s)
{
	int sum=0;
	for(int i=0;i<9;i++)
	{
		sum=sum*10+s[i];
	}
	return sum%Maxsize;
}
int try_to_insert(int s)
{
	int h=hash1(st[s]);
	int u=head[h];
	while(u)
	{
		if(memcmp(st[s],st[u],sizeof(st[s]))==0)
		return 0;
		u=next1[u];
	}
	next1[s]=head[h];
	head[h]=s;
	return 1;
}
int bfs()
{
	init_table();
	int front=1,rear=2;
	while(front<rear)
	{
		State &s=st[front];int z;
		if(memcmp(goal,s,sizeof(s))==0) return front;
		for(int i=0;i<9;i++)
		{
			if(!s[i]) z=i;
		}
		int x=z/3,y=z%3;
		for(int i=0;i<4;i++)
		{
			int newx=x+dx[i];
			int newy=y+dy[i];
			int newz=3*newx+newy;
			if(newx<3&&newx>=0&&newy<3&&newy>=0)
			{
				State &t=st[rear];
				memcpy(&t,&s,sizeof(s));
				t[newz]=s[z];
				t[z]=s[newz];
				dist[rear]=dist[front]+1;
				if(try_to_insert(rear)) rear++;
			}
		}
		front++;
	}
	return 0;
}
int main()
{
	cin>>str1>>str2;
	for(int i=0; i<9; i++) {
		if(str1[i]=='.') 
		st[1][i] = 0;
		else
		st[1][i] = str1[i] - '0';
	}
	for(int i=0; i<9; i++){
		if(str2[i]=='.')
		goal[i] = 0;
		else
		goal[i] = str2[i] - '0';
	} 
	int ans = bfs();
	if(ans == 0) printf("%d\n",-1);
	else 
	printf("%d\n",dist[ans]);
	return 0;
} 
```

0.0分

9 人评分

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

顾亦倾

TA的其他文章

你可能喜欢

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

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

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

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

点我有惊喜！你懂得！

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

评论区

精彩推荐

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

矩形面积交（C语言代码）

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C语言代码）

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

WU-字符串比较（C++代码）

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

DNA （C语言代码）

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

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

1134题解(求分析)

顾亦倾