【题解】洛谷P1379

这道题有很多种方式

A*

A*的核心思想在于设置$k$，即搜索深度，若没有找到就继续向下找

A*的估价函数$\text{check}$，在这题中是统计与标准不同的个数$cnt$，若$cnt+step(已走的步数)>k$，及时结束

// Problem:Luogu P1379 八数码难题

#include<bits/stdc++.h>
using namespace std;
int ans[4][4]=
{
	{0,0,0,0},
	{0,1,2,3},
	{0,8,0,4},
	{0,7,6,5}
};
int a[4][4];
bool found=0;
int dx[]={1,0,0,-1},dy[]={0,-1,1,0},k;
bool same()
{
	for(int i=1;i<4;i++)
		for(int j=1;j<4;j++)
			if(a[i][j]!=ans[i][j])
				return 0;
	return 1;
}
bool check(int step)
{
	int cnt=0;
	for(int i=1;i<4;i++)
		for(int j=1;j<4;j++)
			if(a[i][j]!=ans[i][j])
			{
				if(++cnt+step>k)
					return 0;
			}
	return 1;
}
void A_star(int x,int y,int step,int pre)
{
	if(step==k)
	{
		if(same())found=1;
		return ;
	}
	if(found)return ;
	for(int i=0;i<4;i++)
	{
		int nx=x+dx[i],ny=y+dy[i];
		if(nx<1||ny<1||nx>3||ny>3||i+pre==3)continue;
		swap(a[x][y],a[nx][ny]);
		A_star(nx,ny,step+1,i);
		swap(a[x][y],a[nx][ny]);
	}
}
int main()
{
	int sx,sy;
	string s;
	cin>>s;
	for(int i=0;i<9;i++)
	{
		a[i/3+1][i%3+1]=s[i]-'0';
		if(s[i]=='0')sx=i/3+1,sy=i%3+1;
	}
	if(same()){puts("0");return 0;}
	while(++k)
	{
		A_star(sx,sy,0,-1);
		if(found)
		{
			cout<<k;
			return 0;
		}
	}
}

双向BFS（双端队列BFS）

不需要用整个方阵进行bfs，只要将情况（例如123870456）这样进行bfs

以起点和终点同时进行bfs，能尽快找到

// Problem:Luogu P1379 八数码难题

#include<bits/stdc++.h>
using namespace std;
const int tar=123804765;
int sta;
int mp[4][4];
int read()
{
	int x=0,f=1;
	char c=getchar();
	while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
	while(isdigit(c)){x=x*10+c-'0';c=getchar();}
	return x*f;
}
queue <int> q;
map <int,int> dis,vis;
int dx[]={0,0,1,-1},dy[]={1,-1,0,0};
void bfs()
{
	if(sta==tar)
	{
		puts("0");
		exit(0);
	}
	q.push(sta);
	dis[sta]=0,vis[sta]=1;
	q.push(tar);
	dis[tar]=0,vis[tar]=2;
	while(!q.empty())
	{
		int now=q.front();
		q.pop();
		int tmp=now,x,y;
		for(int i=3;i>=1;i--)
			for(int j=3;j>=1;j--)
			{
				mp[i][j]=tmp%10;
				tmp/=10;
				if(!mp[i][j])x=i,y=j;
			}
		for(int i=0;i<4;i++)
		{
			int nx=x+dx[i],ny=y+dy[i];
			if(nx<1||ny<1||nx>3||ny>3)continue;
			int nxt=0;
			swap(mp[x][y],mp[nx][ny]);
			for(int i=1;i<=3;i++)
				for(int j=1;j<=3;j++)
					nxt=nxt*10+mp[i][j];
			if(vis[nxt]==vis[now])
			{
				swap(mp[x][y],mp[nx][ny]);
				continue;
			}
			if(vis[now]+vis[nxt]==3)
			{
				cout<<dis[now]+dis[nxt]+1;
				exit(0);
			}
			dis[nxt]=dis[now]+1;
			vis[nxt]=vis[now];
			q.push(nxt);
			swap(mp[x][y],mp[nx][ny]);
		}
	}
}
int main()
{
	sta=read();
	bfs();
}

IDA*

dfs的优化，大部分类似懒得讲了

// Problem:Luogu P1379 八数码难题

#include<bits/stdc++.h>
using namespace std;
int ans[4][4]=
{
	{0,0,0,0},
	{0,1,2,3},
	{0,8,0,4},
	{0,7,6,5}
};
int a[4][4],k;
int dx[]={1,0,0,-1},dy[]={0,-1,1,0};
int check()
{
	int cnt=0;
	for(int i=1;i<=3;i++)
		for(int j=1;j<=3;j++)
			cnt+=(a[i][j]!=ans[i][j]);
	return cnt;
}
void dfs(int x,int y,int step,int pre)
{
	int res=check();
	if(!res)
	{
		cout<<step;
		exit(0);
	}
	if(res+step>k)return ;
	for(int i=0;i<4;i++)
	{
		int nx=x+dx[i],ny=y+dy[i];
		if(nx<1||ny<1||nx>3||ny>3||pre+i==3)continue;
		swap(a[x][y],a[nx][ny]);
		dfs(nx,ny,step+1,i);
		swap(a[x][y],a[nx][ny]);
	}
}
int main()
{
	int x,y;
	string s;
	cin>>s;
	for(int i=0;i<s.size();i++)
	{
		a[i/3+1][i%3+1]=s[i]-'0';
		if(s[i]=='0')x=i/3+1,y=i%3+1;
	}
	while(++k)dfs(x,y,0,-1);
}