P5507 题解

· · 题解

前言

题目传送门！

更好的阅读体验？

爆搜题。大家都不用 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;
}

希望能帮助到大家！