自动搬运

查看原文

来自洛谷，原作者为

	arcmiao 时逝作月，月诞爱意

搬运于2025-08-24 22:59:20，当前版本为作者最后更新于2025-03-03 21:26:46，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

BFS

思路

• 本题如果从每一个起点开始 bfs 到终点，在 $10^5$ 次询问下毫无疑问会 TLE，这时我们考虑从终点预处理出到所有可能情况的步数

• 本题选择用一个长度为 ⑨ 的 string 来表示每一种状态，对于一种状态有四种旋转方式（详细见代码），这里用 map<string,int> 来记录到每一种状态的步数

• 接着在询问前做一个从终点开始的 bfs 即可，能以 $O(1)$ 的时间复杂度输出答案

AC Code

#include <bits/stdc++.h>
using namespace std;
string t="123456789";
map<string,int> h; 
void bfs()
{
	queue<string> q;
	q.push(t);
	h[t]=1;
	while(q.size())
	{
		string u=q.front();
		q.pop();
		string v[4]= {u,u,u,u};
		v[0][0]=u[1],v[0][1]=u[4],v[0][3]=u[0],v[0][4]=u[3]; // 左上角
		v[1][1]=u[2],v[1][2]=u[5],v[1][4]=u[1],v[1][5]=u[4]; // 右上角
		v[2][3]=u[4],v[2][4]=u[7],v[2][6]=u[3],v[2][7]=u[6]; // 左下角
		v[3][4]=u[5],v[3][5]=u[8],v[3][7]=u[4],v[3][8]=u[7]; // 右下角
		// 注意这是一个逆推的过程，要逆时针转
		for(int i=0; i<4; i++)
			if(!h[v[i]])
			{
				h[v[i]]=h[u]+1;
				if(v[i]==t) break;
				q.push(v[i]);
			}
	}
}

int main()
{
	int _=1;
	scanf("%d",&_);
	bfs(); // 从终点开始预找出所有可能结果的步数
	while(_--)
	{
		string s;
		for(int i=0; i<9; i++)
		{
			char c;
			scanf(" %c",&c);
			s+=c;
		}
		printf("%d\n",h[s]-1);
	}
	return 0;
}

望审核大大通过！ ๐•ᴗ•๐