• # P5507 机关

题目描述

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

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

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

由于旋钮年久失修，旋转一次很困难，而且时间很紧迫，因此Steve希望用最少的旋转次数打开机关

这个任务就交给你了

输入格式

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

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

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

输出格式

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

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

数据保证有解

数据保证存在打开机关的方式

每个测试点10分

只要你输出格式正确，输出了正确的步数，并给出了任意一种正确方案，就能得到该测试点的得分

否则，该测试点不得分

数据范围：

测试点	所需步数
1	4
2	6
3	8
4	9
5	10
6	11
7	12
8	13
9	15
10	17

思路

首先类似状压DP要设计状态我们让当前旋钮在状态1记作00,状态2记作01，以此类推，总的状态就是 ${\sum }_{i=1}^{12}h(i)\times 2^{i-1}$，$h(i)$ 表示第 $i$ 个旋钮的状态。然后用 A* 算法找到预估最好的路线BFS即可。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1 << 24;//总方案数 
int a[20][10],now[20],fir,g[N + 10],zy[N + 10],choice[N + 10];
struct node{int zt;double f;//估值函数 node(int s):zt(s){double h = 0;f = 0;for(int i = 0;i < 12;i++) {if((s >> (i * 2)) & 3) h += 4 - ((s >> (i * 2)) & 3);}f = g[s] + h / 2;}friend bool operator <(node x,node y) {return x.f > y.f;}
};
priority_queue<node>q;
signed main() {for(int i = 0;i < 12;i++) {scanf("%lld",&now[i]);fir |= (now[i] - 1) << (2 * i);for(int j = 0;j < 4;j++) scanf("%lld",&a[i][j]),a[i][j]--;}g[fir] = 0;q.push(node(fir));while(!q.empty()) {int zt = q.top().zt;q.pop();if(!zt) break;for(int i = 0;i < 12;i++) {int zti = (zt >> (i * 2)) & 3;int ql = (zt >> (a[i][zti] * 2)) & 3;int new_node = zt;new_node ^= zti << (i * 2);new_node ^= ((zti + 1) & 3) << (i * 2);new_node ^= ql << (a[i][zti] * 2);new_node ^= ((ql + 1) & 3) << (a[i][zti] * 2);if(!g[new_node]) {g[new_node] = g[zt] + 1;zy[new_node] = zt;choice[new_node] = i;q.push(node(new_node));}}}printf("%lld\n",g[0]);int ans[20],cnt = g[0];for(int i = 0;i != fir;i = zy[i]) {ans[cnt] = choice[i] + 1;cnt--;}for(int i = 1;i <= g[0];i++) printf("%lld ",ans[i]);return 0;
}