自动搬运

查看原文

来自洛谷，原作者为

	liangbowen 不能再摆了，，，

搬运于2025-08-24 22:11:29，当前版本为作者最后更新于2022-08-30 19:52:15，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

前言

题目传送门！

更好的阅读体验？

爆搜题。大家都不用 Astar 算法，那我来补篇题解。

思路

每个按钮都有状态，因此考虑状压爆搜。

每一个按钮都有 $1, 2, 3, 4$ 几种状态。因此可以转化为 $0, 1, 2, 3$ 四种状态，然后两位一状压。

接下来就是 A 星。估值函数 $h(x)$ 可以设计为：每个按钮分别旋转到 $1$ 的值。由于一次操作会牵动两个按钮，因此要除以二。

//为了方便状压，数组、按钮编号，下标都从1开始
struct node
{
	int st; //状态 
	double f;
	node(int zltqwq)
	{
		db h = 0;
		st = zltqwq;   //下面 &3 可以简单理解为 mod 4
		for (int i = 0; i < 12; i++) h += (4 - ((st >> (i * 2)) & 3)) & 3; 
		h /= 2;
		f = g[st] + h;	
	}
	friend bool operator <(node y, node x) {return x.f < y.f;}
};
priority_queue <node> q;

定义好后，输入时记录一下初始状态。然后开始爆搜。

int IAKIOI; //想不到好的名字了。反正是初始状态
void input()
{
	for (int i = 0; i < 12; i++)
	{   //下标统一减一
		int a = read() - 1; IAKIOI |= (a << (i * 2));
		for (int j = 0; j < 4; j++) nxt[i][j] = read() - 1; 
	}	
}

每次枚举每一个状态下，对应的每一个按钮的状态。同时记录每一个按钮受牵动的按钮编号及其对应状态。

然后通过异或性质（$x \oplus x = 0$）将下一个状态求出。这一部分其实很容易，只是代码实现看起来比较罢了。

这个状态没有访问过就更新。由于最后要输出方案，所以记录一下状态是由哪一个状态，旋转什么按钮得到的。

int IAKIOI; //初始状态 
void Astar()
{
    priority_queue <node> q;
    q.push(node(IAKIOI)), vis[IAKIOI] = true;
    while (!q.empty())
    {
        int st = q.top().st;
        //printf("st = %d\n", st);
        q.pop();
        if (st == 0) break; //等同于全是1
        for (int i = 0; i < 12; i++)
        {
        	//分别表示i的状态，受牵连的按钮编号，受牵连的按钮的状态
            int sti = (st >> (i * 2)) & 3, di = nxt[i][sti], stdi = (st >> (di * 2)) & 3; 
            //其实就是将第i个按钮替换成下一个状态。当前状态为 sti，下一个状态显然是 (sti + 1) % 4
         	int dst = st ^ (sti << (i * 2)) ^ (((sti + 1) & 3) << (i * 2));
         	//同上，就是将第di个按钮替换成下一个状态。当前状态为 stdi，下一个状态显然是 (stdi + 1) % 4
            dst = dst ^ (stdi << (di * 2)) ^ (((stdi + 1) & 3) << (di * 2));
            if (!vis[dst]) //没有就进去
            {
				//pre[] 和 button[] 分别表示：从哪个状态过来；从那个状态过来是使用什么按钮 
                g[dst] = g[st] + 1, vis[dst] = true;
                pre[dst] = st, button[dst] = i + 1;
                q.push(node(dst));
            }
        }
    }
}

然后输出就完事了。用递归的形式倒序输出即可。

void output(int x)
{
	if (x == IAKIOI) return;
	output(pre[x]), write(button[x]), space;
}
int main()
{
	input();
	Astar();
	write(g[0]), endl; //0是最终状态
	output(0);
	return 0;
}

这道题就做完啦！

完整代码

#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;
int read()
{
	char op = getchar(); int x = 0, f = 1;
	while (op < 48 || op > 57) {if (op == '-') f = -1; op = getchar();}
	while (48 <= op && op <= 57) x = (x << 1) + (x << 3) + (op ^ 48), op = getchar();
	return x * f;
}
const int k = 1 << 24;
int nxt[15][10], g[k + 10];
bool vis[k + 10];
int pre[k + 10], button[k + 10]; //分别表示：从哪个状态过来；从那个状态过来是使用什么按钮 
struct node
{
	int st; //状态 
	double f;
	node(int zltqwq) //变量起 @zltqwq 是因为想不到好名字了。膜拜 zlt
	{
		double h = 0;
		st = zltqwq;
		for (int i = 0; i < 12; i++) h += (4 - ((st >> (i * 2)) & 3)) & 3;
		h /= 2;
		f = g[st] + h;	
	}
	friend bool operator <(node y, node x) {return x.f < y.f;}
};
int IAKIOI; //初始状态 
void Astar()
{
	priority_queue <node> q;
	q.push(node(IAKIOI)), vis[IAKIOI] = true;
	while (!q.empty())
	{
		int st = q.top().st;
		//printf("st = %d\n", st);
		q.pop();
		if (st == 0) break; //等同于全是1
		for (int i = 0; i < 12; i++)
		{
			int sti = (st >> (i * 2)) & 3, di = nxt[i][sti], stdi = (st >> (di * 2)) & 3;
			int dst = st ^ (sti << (i * 2)) ^ (((sti + 1) & 3) << (i * 2));
			dst = dst ^ (stdi << (di * 2)) ^ (((stdi + 1) & 3) << (di * 2));
			if (!vis[dst])
			{
				g[dst] = g[st] + 1, vis[dst] = true;
				pre[dst] = st, button[dst] = i + 1;
				q.push(node(dst));
			}
		}
	}
}
void input()
{
	for (int i = 0; i < 12; i++)
	{
		int a = read() - 1;
        IAKIOI |= (a << (i * 2));
		for (int j = 0; j < 4; j++) nxt[i][j] = read() - 1;
	}	
}
void output(int x)
{
	if (x == IAKIOI) return;
	output(pre[x]), printf("%d ", button[x]);
}
int main()
{
	input();
	Astar();
	printf("%d\n", g[0]); //0是最终状态
	output(0);
	return 0;
}

希望能帮助到大家！