官方题解

题目大意

有 $9$ 个点 $m$ 条边的无向图，其中有 $8$ 个数字放置在不同点上，有一个没有数字的点，可以通过移动将数字移动到相邻没有数字的点上，求最终将数字 $1\sim 8$ 分别放在顶点 $1\sim 8$ 上的最少操作次数。

解题思路

我们可以将 $9$ 个顶点上所存放的数字用字符串表示状态，例如 254806137 表示顶点 $1$ 存放数字 $2$ ，顶点 $2$ 存放数字 $5$ ，依此类推，特殊地，数字 $0$ 表示该点为空。那么终点就可以用 123456780 表示。

由于每次移动都会从一种状态变为另一种状态，我们不妨将每种状态看作一个结点，那么所有状态以及状态与状态之间的变换就可以形成一张无向图，于是我们只需要在图上用 $bfs$ 跑最短路即可。由于结点是以字符串表示的，所以可以使用 map 存储从起点状态到达所有状态结点的最短路径长度。

参考代码

#include <bits/stdc++.h>
using namespace std;
const int N = 200010;

vector<int>v[N];

int main(){
	int m;cin>>m;
	for(int i=1;i<=m;i++){
		int a,b;cin>>a>>b;
		v[a].push_back(b);
		v[b].push_back(a);
	}
	string s=" 000000000";
	for(int i=1;i<=8;i++){
		int x;cin>>x;
		s[x]=i+'0';
	}

	queue<string>q;
	map<string,bool>vis;
	map<string,int>d;
	q.push(s);
	vis[s]=true;
	d[s]=0;
	while(!q.empty()){
		auto t=q.front();q.pop();

		int pos=t.find('0');
		for(auto x:v[pos]){
			string tmp=t;
			tmp[x]=t[pos];
			tmp[pos]=t[x];

			if(vis[tmp]) continue;
			q.push(tmp);
            
			vis[tmp]=true;
			d[tmp]=d[t]+1;
		}
	}
	if(vis[" 123456780"]) cout<<d[" 123456780"]<<endl;
	else cout<<-1<<endl;
}