• # 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;
}