最直接的原因是：你把初始栈建反了。
你后面的所有操作都把 vector::back() 当成栈顶：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| vector<L_R_A_B_C> op_lrabc() const {
vector<L_R_A_B_C> res;
for (int i = 0; i < 2; ++i) {
if (hands[i] == 0) continue;
for (int j = 0; j < 3; ++j) {
if (tower_ls[j].empty() || tower_ls[j].back() > hands[i]) {
L_R_A_B_C to = *this;
to.tower_ls[j].push_back(hands[i]);
to.hands[i] = 0;
res.push_back(to);
}
}
}
for (int i = 0; i < 2; ++i) {
if (hands[i] != 0) continue;
for (int j = 0; j < 3; ++j) {
if (tower_ls[j].empty()) continue;
L_R_A_B_C to = *this;
to.hands[i] = tower_ls[j].back();
to.tower_ls[j].pop_back();
to.step++;
res.push_back(to);
}
}
return res;
}
|
但你初始化的时候写的是：
1
2
3
4
5
6
7
8
9
| ll bfs(ll n) {
L_R_A_B_C st;
for (int i = 1; i <= n; ++i) {
st.tower_ls[0].push_back(i);
}
set<L_R_A_B_C> memo;
priority_queue<L_R_A_B_C> q;
q.push(st);
memo.insert(st);
|
这样 A 里实际是 [1,2,3,...,n]，而 back() 是 n。
也就是说，你程序理解出来的“栈顶”是最大的盘，这和题意“越靠近栈底越大”正好反了。
所以你的程序会认为可以这样合法移动：
-
先拿出 n 放到空的 C
-
再拿出 n-1 放到 C，因为此时 C.back() = n > n-1
-
再拿出 n-2
-
一直这样下去
于是每个盘都只需要被拿起一次，答案自然就成了 n，所以你才会打出：
你这里概念上应该让初始 A 满足：如果 back() 是栈顶，那么 back() 必须是最小盘，也就是初始内容应当是 {n,n-1,...,1}，而不是 {1,2,...,n}。