【题目来源】
洛谷：P5507 机关 - 洛谷
【题目描述】
这扇门上有一个机关，上面一共有 \(12\) 个旋钮，每个旋钮有 \(4\) 个状态，将旋钮的状态用数字 \(1\) 到 \(4\) 表示。
每个旋钮只能向一个方向旋转（状态：\(1\rightarrow2\rightarrow3\rightarrow4\rightarrow1\)），在旋转时，会引起另一个旋钮也旋转一次（方向相同，不会引起连锁反应），同一旋钮在不同状态下，可能会引起不同的旋钮旋转（在输入中给出）。
当所有旋钮都旋转到状态 \(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\) 个整数，表示依次旋转的旋钮编号。
数据保证有解。
【输入样例】
3 3 7 2 6
3 1 4 5 3
3 1 2 6 4
3 1 10 3 5
3 2 8 3 6
3 7 9 2 1
1 1 2 3 4
1 3 11 10 12
1 8 6 7 4
1 9 9 8 8
1 12 10 12 12
1 7 8 9 10
【输出样例】
6
1 2 3 4 5 6
【算法标签】
《洛谷 P5507 机关》 #搜索# #广度优先搜索BFS# #启发式搜索# #Special Judge# #O2优化#
【代码详解】
// 40分版本
#include <bits/stdc++.h>
using namespace std;int a[15][5]; // 存储状态转移表
map<long long, bool> m; // 记录访问过的状态// 节点结构体
struct Node
{int x[15]; // 当前状态数组int path[20] = {}; // 路径记录int step = 0; // 步数
} n, t; // n: 当前节点, t: 临时节点// 将状态数组转换为一个长整型数字，用于快速比较和存储
long long num(int x[])
{long long s = 0;for (int i = 1; i <= 12; i++)s = s * 10 + x[i];return s;
}// 广度优先搜索
void bfs(Node n)
{queue<Node> q;q.push(n);long long b;while (!q.empty()){t = n = q.front(); // 取出队列头节点q.pop();for (int i = 1; i <= 12; i++) // 尝试对每个位置进行操作{// 执行操作：更新状态n.x[a[i][n.x[i]]]++; // 根据当前值更新相关位置if (n.x[a[i][n.x[i]]] == 5) n.x[a[i][n.x[i]]] = 1; // 超过4则回到1n.x[i]++; // 当前位置加1if (n.x[i] == 5) n.x[i] = 1; // 超过4则回到1b = num(n.x); // 计算新状态的数字表示if (m[b]) // 如果状态已访问过{n = t; // 恢复状态continue;}m[b] = 1; // 标记为已访问n.path[n.step++] = i; // 记录操作位置if (b == 111111111111) // 目标状态检查{cout << n.step << endl; // 输出步数for (int j = 0; j < n.step; j++)cout << n.path[j] << " "; // 输出路径cout << endl;return;}q.push(n); // 新状态入队n = t; // 恢复状态，尝试下一个操作}}
}int main()
{// 输入状态转移表for (int i = 1; i <= 12; i++)for (int j = 0; j < 5; j++)cin >> a[i][j];// 初始化起始状态for (int i = 1; i <= 12; i++)n.x[i] = a[i][0];m[num(n.x)] = 1; // 标记起始状态为已访问bfs(n); // 开始搜索return 0;
}
// 满分做法
#include <bits/stdc++.h>
using namespace std;int a[15][5], m[20000005]; // a: 转移表, m: 访问标记数组
struct Node
{int x[15], path[20] = {}, step = 0; // x: 当前状态, path: 路径, step: 步数// 重载()运算符，用于优先队列的优先级比较bool operator () (Node a, Node b) const{int sa = 0, sb = 0;for (int i = 1; i <= 12; i++){sa += (5 - a.x[i]) % 4; // 启发函数h(n) = 距离目标状态的估计代价sb += (5 - b.x[i]) % 4;}return sa/2 + a.step > sb/2 + b.step; // 比较f(n)=g(n)+h(n)}
} n, t; // n: 当前节点, t: 临时节点// 将状态数组压缩为一个整数
int num(int x[])
{long long s = 0;for (int i = 1; i <= 12; i++)s = s * 4 + (x[i] - 1); // 将1-4的值转换为0-3return s;
}// A*搜索算法
void bfs(Node n)
{priority_queue<Node, vector<Node>, Node> q; // 优先队列q.push(n);int c[13] = {0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}; // 目标状态int b, r = num(c); // 计算目标状态的编号while (!q.empty()){t = n = q.top(); // 取出优先级最高的节点q.pop();for (int i = 1; i <= 12; i++) // 尝试所有可能的操作{// 执行操作in.x[a[i][n.x[i]]]++; // 更新相关位置if (n.x[a[i][n.x[i]]] == 5) n.x[a[i][n.x[i]]] = 1;n.x[i]++; // 更新当前位置if (n.x[i] == 5) n.x[i] = 1;b = num(n.x); // 计算新状态的编号if (m[b]) // 如果已访问过{n = t; // 恢复状态continue;}m[b] = 1; // 标记为已访问n.path[n.step++] = i; // 记录操作if (b == r) // 到达目标状态{cout << n.step << endl; // 输出步数for (int j = 0; j < n.step; j++)cout << n.path[j] << " "; // 输出路径cout << endl;return;}q.push(n); // 新节点加入队列n = t; // 恢复状态}}
}int main()
{// 输入转移表for (int i = 1; i <= 12; i++)for (int j = 0; j < 5; j++)cin >> a[i][j];// 初始化起始状态for (int i = 1; i <= 12; i++)n.x[i] = a[i][0];m[num(n.x)] = 1; // 标记起始状态bfs(n); // 开始搜索return 0;
}
【运行结果】
3 3 7 2 6
3 1 4 5 3
3 1 2 6 4
3 1 10 3 5
3 2 8 3 6
3 7 9 2 1
1 1 2 3 4
1 3 11 10 12
1 8 6 7 4
1 9 9 8 8
1 12 10 12 12
1 7 8 9 10
6
1 1 2 3 4 5