洛谷P5507 机关题解

题意：

cxy 成功脱单后，在npy家里发现了一扇暗门，但是这扇门是锁着的

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

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

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

由于旋钮年久失修，旋转一次很困难，而且时间很紧迫（指想和npy去贴贴）

因此她希望用最少的旋转次数打开机关，这个任务就交给你了

输入格式：

$12$ 行，每行 $5$ 个整数，描述机关的状态

第 $i$ 行第一个整数 $s_i$ 表示第 $i$ 个旋钮的初始状态是 $s_i$

接下来 $4$ 个整数 $a_{i,j},j=1,2,3,4$ 表示这个旋钮在状态 $j$ 时旋转，会引起第 $a_{i,j}$ 个旋钮旋转到下一个状态

输出格式：

第一行一个整数 $n$，表示最少的步数

第二行 $n$ 个整数，表示依次旋转的旋钮编号

数据保证有解

数据范围：

所需步数 ≤ 17 。

貌似就是暴搜剪枝，这里我用的是双向bfs（我才不写 A-star 呢）

考虑状压每个按钮的状态，这里用到了四进制压缩的方法（两个2当一个4）

另外，双向bfs不是折半搜索(meet in the middle) 啊，折半搜索需要合并两侧搜索结果，这里合并啥啊。

时间复杂度 $\mathcal{o}(12^{k / 2})$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }

#define N ((int)((1 << 24) + 5))

queue<int> q;
char ok,type[N],vis[N];
int m1,m2,key,nxt[15][6],fa[N],choice[N],ans1[25],ans2[25];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int start = 0; const int end = 0;
    for(int i = 0,x; i < 12; i++)
    {
        cin >> x; start |= (x - 1) << (i << 1);
        for(int j = 0; j < 4; j++) { cin >> nxt[i][j]; --nxt[i][j]; }
    }
    vis[start] = vis[end] = 1; type[start] = 1; type[end] = 2;
    for(q.push(start), q.push(end); !q.empty() && !ok; )
    {
        int st = q.front(), tp = type[st]; q.pop();
        static int i, j, si, sj, next_st;
        for(i = 0; i < 12; i++)
        {
            if(tp == 1)
            {
                si = (st >> (i << 1)) & 3; // state of i
                j = nxt[i][si];
                sj = (st >> (j << 1)) & 3; // state of j
                next_st = st ^ (si << (i << 1)) ^ (((si + 1) & 3) << (i << 1));
                next_st ^= (sj << (j << 1)) ^ (((sj + 1) & 3) << (j << 1));
            }else
            {
                si = (st >> (i << 1)) & 3;
                j = nxt[i][(si + 3) & 3];
                sj = (st >> (j << 1)) & 3;
                next_st = st ^ (si << (i << 1)) ^ (((si + 3) & 3) << (i << 1));
                next_st ^= (sj << (j << 1)) ^ (((sj + 3) & 3) << (j << 1));
            }
            if(vis[next_st])
            {
                if(type[next_st] == tp) continue;
                m1 = ((tp == 1) ? st : next_st); key = i + 1;
                m2 = ((tp == 2) ? st : next_st); ok = 1; break;
            }
            vis[next_st] = 1; type[next_st] = tp;
            fa[next_st] = st; choice[next_st] = i;
            q.push(next_st);
        }
    }
    int cnt1 = 0, cnt2 = 0;
    for(int u = m1; u != start; u = fa[u]) ans1[++cnt1] = choice[u] + 1;
    for(int u = m2; u != end; u = fa[u]) ans2[++cnt2] = choice[u] + 1;
    cout << (cnt1 + cnt2 + 1) << '\n';
    for(int i = cnt1; i; i--) cout << ans1[i] << ' ';
    cout << key << ' ';
    for(int i = 1; i <= cnt2; i++) cout << ans2[i] << " \n"[i == cnt2];
    return 0;
}