《P5507 机关》
题目背景
Steve成功降落后，在M星上发现了一扇大门，但是这扇大门是锁着的
题目描述
这扇门上有一个机关，上面一共有12个旋钮，每个旋钮有4个状态，将旋钮的状态用数字1到4表示
每个旋钮只能向一个方向旋转（状态：1->2->3->4->1），在旋转时，会引起另一个旋钮也旋转一次（方向相同，不会引起连锁反应），同一旋钮在不同状态下，可能会引起不同的旋钮旋转（在输入中给出）
当所有旋钮都旋转到状态1时，机关就打开了
由于旋钮年久失修，旋转一次很困难，而且时间很紧迫，因此Steve希望用最少的旋转次数打开机关
这个任务就交给你了
输入格式
12行，每行5个整数，描述机关的状态
第i行第一个整数si表示第i个旋钮的初始状态是si
接下来4个整数ai,j,j=1,2,3,4表示这个旋钮在状态j时旋转，会引起第ai,j个旋钮旋转到下一个状态
输出格式
第一行一个整数n，表示最少的步数
第二行n个整数，表示依次旋转的旋钮编号
数据保证有解
输入输出样例
输入 #1复制
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
输出 #1复制
6 1 2 3 4 5 6
输入 #2复制
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
输出 #2复制
6 1 1 2 3 4 5
输入 #3复制
4 2 2 2 2 4 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
输出 #3复制
1 1
输入 #4复制
4 9 3 4 5 1 9 8 12 11 4 7 5 6 12 3 2 2 11 2 3 6 8 2 12 4 8 4 2 11 2 12 9 5 3 4 1 1 11 1 1 1 7 4 1 4 11 6 12 8 2 6 3 7 6 4 3 9 7 10
输出 #4复制
10 11 4 6 10 7 7 5 9 9 9
说明/提示
样例1和2输入相同，两个输出都可以通过
样例4解释：
414334 241424
旋转11到状态3，引起3旋转到状态1
411334 241434
旋转4到状态4，引起11旋转到状态4
411434 241444
旋转6到状态1，引起11旋转到状态1
411431 241414
旋转10到状态1，引起8旋转到状态1
411431 211114
旋转7到状态3，引起9旋转到状态2
411431 312114
旋转7到状态4，引起5旋转到状态4
411441 412114
旋转5到状态1，引起12旋转到状态1
411411 412111
旋转9到状态3，引起7旋转到状态1
411411 113111
旋转9到状态4，引起4旋转到状态1
411111 114111
旋转9到状态1，引起1旋转到状态1
111111 111111
数据保证存在打开机关的方式
每个测试点10分
只要你输出格式正确，输出了正确的步数，并给出了任意一种正确方案，就能得到该测试点的得分
否则，该测试点不得分
数据范围：
| 测试点 | 所需步数 |
|---|---|
| 1 | 4 |
| 2 | 6 |
| 3 | 8 |
| 4 | 9 |
| 5 | 10 |
| 6 | 11 |
| 7 | 12 |
| 8 | 13 |
| 9 | 15 |
| 10 | 17 |
代码实现：
#include <iostream>
#include <vector>
#include <queue>
#include <map> // 替代unordered_map
#include <string>
using namespace std;
// 状态表示：使用12位4进制数，每位代表一个旋钮的状态
int stateToNum(vector<int>& state) {
int num = 0;
for (int i = 0; i < 12; i++) {
num = num * 4 + (state[i] - 1); // 状态1-4转换为0-3
}
return num;
}
// 数字转换为状态
void numToState(int num, vector<int>& state) {
for (int i = 11; i >= 0; i--) {
state[i] = num % 4 + 1; // 0-3转换回1-4
num /= 4;
}
}
// 自定义三元组结构替代tuple
struct Node {
int state;
vector<int> ops;
int steps;
Node(int s, const vector<int>& o, int st) : state(s), ops(o), steps(st) {}
};
int main() {
// 读取初始状态和转移规则
vector<int> initialState(12);
vector<vector<int> > trans(12, vector<int>(5)); // trans[i][j]表示第i个旋钮在状态j时旋转引起的旋钮
for (int i = 0; i < 12; i++) {
cin >> trans[i][0]; // trans[i][0]是初始状态s_i
initialState[i] = trans[i][0];
for (int j = 1; j <= 4; j++) {
cin >> trans[i][j]; // trans[i][j]表示状态j时引起的旋钮
}
}
// 目标状态：全1
vector<int> targetState(12, 1);
int targetNum = stateToNum(targetState);
// BFS队列
queue<Node> q;
// 记录访问过的状态
map<int, bool> visited;
// 初始状态入队
int initialNum = stateToNum(initialState);
q.push(Node(initialNum, vector<int>(), 0));
visited[initialNum] = true;
while (!q.empty()) {
Node current = q.front();
q.pop();
int currState = current.state;
vector<int> ops = current.ops;
int steps = current.steps;
// 检查是否达到目标状态
if (currState == targetNum) {
// 输出结果
cout << steps << endl;
for (int i = 0; i < ops.size(); i++) {
if (i > 0) cout << " ";
cout << ops[i] + 1; // 旋钮编号从1开始
}
cout << endl;
return 0;
}
// 尝试旋转每个旋钮
vector<int> currStateVec(12);
numToState(currState, currStateVec);
for (int i = 0; i < 12; i++) {
int currStateOfKnob = currStateVec[i]; // 当前旋钮状态
int affectedKnob = trans[i][currStateOfKnob] - 1; // 引起旋转的旋钮(转换为0-11)
// 复制当前状态并更新
vector<int> newState = currStateVec;
// 旋转当前旋钮
newState[i] = (newState[i] % 4) + 1;
// 旋转受影响的旋钮
newState[affectedKnob] = (newState[affectedKnob] % 4) + 1;
int newStateNum = stateToNum(newState);
// 如果新状态未访问过，则入队
if (visited.find(newStateNum) == visited.end()) {
vector<int> newOps = ops;
newOps.push_back(i);
q.push(Node(newStateNum, newOps, steps + 1));
visited[newStateNum] = true;
}
}
}
return 0;
}