解题报告 P5507 机关

题目内容

P5507

大意：这扇门上有一个机关，上面一共有12个旋钮，每个旋钮有4个状态，将旋钮的状态用数字1到4表示

每个旋钮只能向一个方向旋转（状态：1->2->3->4->1），在旋转时，会引起另一个旋钮也旋转一次（方向相同，不会引起连锁反应），同一旋钮在不同状态下，可能会引起不同的旋钮旋转（在输入中给出）

当所有旋钮都旋转到状态1时，机关就打开了

求最少打开门的次数

解题思路

搜索，但是由于极高的复杂度，肯定是不能用一般的搜索的。

然后可以使用 A*，卡卡常可以过去，A* 的估价函数设为当前步数加上旋钮与 1 差的步数之和除以二向上取整。因为考虑最优情况：转一个旋钮可以带动两个，所以这个估价函数是比较不错的。

A* 的实现使用优先队列即可，好像这题吸氧没什么卵用

判重由于我不会写 hash，就搞了个 12 维的 bool 数组，计算器告诉我们空间能过（好了我要滚去学状态优化了）。

其实这题还可以用双向 bfs，因为初始状态和终止状态都是已知的

复杂度 O(玄学)

代码：

#include <cstdio>
#include <cctype>
#include <queue>
#define vis(x) (v[x.s[1]%4][x.s[2]%4][x.s[3]%4][x.s[4]%4][x.s[5]%4][x.s[6]%4][x.s[7]%4][x.s[8]%4][x.s[9]%4][x.s[10]%4][x.s[11]%4][x.s[12]%4])
using namespace std;

struct node
{
    int q[19];
    int s[13];
    int step;
    int chk;
};

inline void nxt(int &a)//将这个旋钮转一下
{
    a=(a+1)%4==0?4:(a+1)%4;
    return;
}

inline int read()
{
    char c=getchar();
    int s=0;
    while(!isdigit(c))
        c=getchar();
    while(isdigit(c))
        s=10*s+c-'0',c=getchar();
    return s;
}

int a[13][5];
bool v[4][4][4][4][4][4][4][4][4][4][4][4];//巨长的 vis 数组

inline int h(node &x)//估价函数
{
    int ans=0;
    for(int i=1;i<=12;i++)
        ans+=x.s[i]==1?0:5-x.s[i];
    return (ans-1>>1)+1;
}

inline int check(node &x)//检查是否到达了最终状态
{
    for(int i=1;i<=12;i++)
        if(x.s[i]!=1)
            return false;
    return true;
}

bool operator>(const node &a,const node &b)//重载大于号
{
    return a.chk>b.chk;
}

void astar(node st)
{
    priority_queue<node,vector<node>,greater<node> > q;
    q.push(st);
    while(!q.empty())
    {
        node now=q.top();
        q.pop();
        if(check(now))
        {
            printf("%d\n",now.step);
            for(int i=1;i<=now.step;i++)
                printf("%d ",now.q[i]);
            return;
        }
        if(vis(now))
            continue;
        else
        {
            vis(now)=1;
            node nextone=now;
            for(int i=1;i<=12;i++)//状态转移
            {
                nxt(nextone.s[a[i][nextone.s[i]]]);
                nxt(nextone.s[i]);
                nextone.q[++nextone.step]=i;
                nextone.chk=h(nextone)+nextone.step;
                q.push(nextone);
                nextone.s[i]=now.s[i];
                nextone.s[a[i][nextone.s[i]]]=now.s[a[i][nextone.s[i]]];
                nextone.step--;
            }
        }
    }
}

int main()
{
    node st;
    for(int i=1;i<=12;i++)
    {
        for(int j=0;j<=4;j++)
            a[i][j]=read();
        st.s[i]=a[i][0];
    }
    st.chk=h(st);
    st.step=0;
    astar(st);
    return 0;
}