题目描述

在3×3的棋盘上，摆有八个棋子，每个棋子上标有1至8的某一数字。棋盘中留有一个空格，空格用0来表示。空格周围的棋子可以移到空格中。要求解的问题是：给出一种初始布局（初始状态）和目标布局（为了使题目简单,设目标状态为123804765），找到一种最少步骤的移动方法，实现从初始布局到目标布局的转变。

输入格式

输入初始状态，一行九个数字，空格用0表示

输出格式

只有一行，该行只有一个数字，表示从初始状态到目标状态需要的最少移动次数(测试数据中无特殊无法到达目标状态数据)

输入输出样例

输入 #1

283104765

输出 #1

4

原题目链接：https://www.luogu.com.cn/problem/P1379

八数码问题是一道很经典的题，涉及到的知识面很广，所以八数码是一道经典题。

这里我先写了个双向bfs的算法，分别从起始状态和最终状态两个地方进行bfs(爱是双向的奔赴)，再配合上hash判重复状态，254ms通过，不多比比上代码

#include <queue>
#include <map>
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#define ll long long
using namespace std;
map<ll,ll>c;
map<ll,ll>sum;
int dir1[]={0,0,1,-1},dir2[]={-1,1,0,0};
int dir[1];
struct node{
	int a[4][4];//地图
	int nx,ny;//0的坐标
	int step,s;//step步数，s代表了从起点或者终点出发
};
node e;
ll hash(node now){
	ll ans=0;
	for(int i=1;i<=3;i++)
		for(int j=1;j<=3;j++){
			ans=ans*10+now.a[i][j];
		}
	return ans;
}//此函数可以将矩阵里的数字转化为一个大数字代表一种状态
void bfs(node t){
	e.a[1][1]=1,e.a[1][2]=2,e.a[1][3]=3,
	e.a[2][1]=8,e.a[2][2]=0,e.a[2][3]=4,
	e.a[3][1]=7,e.a[3][2]=6,e.a[3][3]=5;//设置终点状态
	e.nx=2,e.ny=2,e.step=1,e.s=2;
	t.s=1;
	//printf("%lld %lld\n",hash(t),hash(e));
	c[hash(t)]=1,c[hash(e)]=2;//c用来记录某一种状态是从起点搜到的还是终点搜到的
	sum[hash(t)]=0,sum[hash(e)]=1;//sum计步数
	if(hash(t)==hash(e)) {printf("0");return ;}//特判
	queue<node>q;
	q.push(t),q.push(e);
	//printf("%d %d\n",t.nx,t.ny);
	while(q.size()){
		node now=q.front();
		ll nhas=hash(now);
		q.pop();
		for(int i=0;i<4;i++){
			node nxt=now;
			for(int j=1;j<=3;j++)
				for(int k=1;k<=3;k++)
					nxt.a[j][k]=now.a[j][k];
			nxt.nx+=dir1[i],nxt.ny+=dir2[i];
			nxt.step+=1;
			swap(nxt.a[nxt.nx][nxt.ny],nxt.a[now.nx][now.ny]);
			ll has=hash(nxt);
			if(nxt.nx<1||nxt.nx>3||nxt.ny<1||nxt.ny>3) continue;//判断是否出界
			//printf("%lld %d %d\n",has,nxt.step,nxt.s);
		//	if(has==283104765) printf("%lld %lld %lld\n",c[has],c[nhas],nhas);
		//	if(has==123405678) printf("%lld %lld %lld\n",c[has],c[nhas],nhas);
			if(c[has]==c[nhas]) continue;//如果是同一根源搜到的状态那么说明是走回头路了
			if(c[has]+c[nhas]==3){//来自不同根源的搜索，找到答案了
				printf("%lld",sum[has]+sum[nhas]);
				return;
			}

			c[has]=now.s;
			sum[has]=now.step+1;
			q.push(nxt);
		}
	}
}
int main(){
	node t;
	char s[10];
	scanf("%s",s);
	for(int i=0;i<(strlen(s));i++){
		t.a[i/3+1][i%3+1]=s[i]-'0';
		if(!(s[i]-'0')) t.nx=i/3+1,t.ny=i%3+1;
	}
	t.step=0;
	bfs(t);
	return 0;
}