题目描述
这里有 n 列火车将要进站再出站,但是,每列火车只有 1 节,那就是车头。
这 n 列火车按 1 到 n 的顺序从东方左转进站,这个车站是南北方向的,它虽然无限长,只可惜是一个死胡同,而且站台只有一条股道,火车只能倒着从西方出去,而且每列火车必须进站,先进后出。
也就是说这个火车站其实就相当于一个栈,每次可以让右侧头火车进栈,或者让栈顶火车出站。
车站示意如图:
出站<—— <——进站
|车|
|站|
|__|
现在请你按《字典序》输出前 20 种可能的出栈方案。
输入格式
输入一个整数 n,代表火车数量。
输出格式
按照《字典序》输出前 20 种答案,每行一种,不要空格。
输入样例
3
输出样例
123
132
213
231
321
栈的简单操作:
在这里直接dfs搜索所有可能方案
三个状态
state1:表示出栈的序列
state2:栈里的元素
state3:剩余未进栈的元素
边界条件
state1的长度等于n 且 state2和state3都为空
可能的操作
1,state3中的元素进入state2中(即入栈操作)
2,state2中的元素进入state1中(即出栈操作)
字典序的要求
为了保证答案按照字典序输出
我们可以发现就是要尽量让在前面的数字尽可能的小
所以我们要先执行操作 2。
如果我们先执行操作1的话那么入栈的数字一定比当前state2的栈顶元素来的大
这样之后出栈的元素也会比当前state2的栈顶元素来的大
所以我们先执行操作2
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <stack>
using namespace std;
int n, cnt = 20;//题目要求前20种答案
//对应三种状态
vector<int> state1;
stack<int> state2;
int state3 = 1;//初始值为1
void dfs()
{
if(!cnt) return;//如果超过20种方案就不输出了
if(state1.size() == n)//边界条件
{
cnt -- ;//每输出一个元素就减一
for(auto x : state1) cout << x;
cout << endl;
return;
}
if(state2.size())//先执行操作2---出栈
{
state1.push_back(state2.top());
state2.pop();
dfs();
state2.push(state1.back());//恢复状态
state1.pop_back();
}
if(state3 <= n)//操作1
{
state2.push(state3);
state3 ++ ;
dfs();
state3 -- ;
state2.pop();
}
}
int main()
{
cin >> n;
dfs();
return 0;
}