火车进栈

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int N = 30;
 4 int n;
 5 int cnt = 20;
 6 vector<int> state1; //已出栈的火车序列
 7 stack<int> state2; //已入栈的火车序列
 8 int state3 = 1; //未入栈的火车,注意初始值为1
 9 void dfs() {
10     if (!cnt) { //如果cnt减为0了
11         return;
12     }
13     if (state1.size() == n) { //如果全部出栈了
14         cnt--;
15         for (int i = 0; i < state1.size(); i++) {
16             cout << state1[i];
17         }
18         cout << endl;
19         return;
20     }
21     //枚举两种操作
22     //为保证字典序，先枚举出栈，后枚举入栈
23     if (state2.size()) { //开始枚举出栈
24         state1.push_back(state2.top());
25         state2.pop();
26         dfs();
27         //恢复现场
28         state2.push(state1.back());
29         state1.pop_back();
30     }
31     if (state3 <= n) { //开始枚举入栈
32         //state3 <= n表示还有火车没有入栈
33         state2.push(state3);
34         state3++;
35         dfs();
36         //恢复现场
37         state2.pop();
38         state3--;
39     }
40 }
41 int main() {
42     cin >> n;
43     dfs();
44     return 0;
45 }