博客

火车进栈


这里有n列火车将要进站再出站，但是，每列火车只有1节，那就是车头。

这n列火车按1到n的顺序从东方左转进站，这个车站是南北方向的，它虽然无限长，只可惜是一个死胡同，而且站台只有一条股道，火车只能倒着从西方出去，而且每列火车必须进站，先进后出。

也就是说这个火车站其实就相当于一个栈，每次可以让右侧头火车进栈，或者让栈顶火车出站。

车站示意如图：

        出站<——    <——进站
                 |车|
                 |站|
                 |__|

现在请你按《字典序》输出前20种可能的出栈方案。

输入格式

输入一个整数n，代表火车数量。

输出格式

按照《字典序》输出前20种答案，每行一种，不要空格。

数据范围

1≤n≤20

输入样例：

3

输出样例：

123

132

213

231

321

#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
using namespace std;
int n,remain=20; //n为我们输入的限定的元素的个数,remain为当前输出个数的上限
//本题我们可以很明显的看到：
//(1)用模拟的方法模拟栈的入栈和出栈的操作
//(2)因为每一步都有入栈和出栈的两种操作的选择，因此我们要用到dfs的方法求解 
vector<int > path;//path向量用于暂时存储出栈的元素
stack<int > stk;//stk为实际操作栈 
void dfs(int u)
{//这里dfs的参数u只有表示当前可以入栈的元素的大小的意义，由此我们还可以判断是否能入栈
if(!remain)//当输出个数达到上限时 
{
return;
}
if(path.size()==n)
{//当栈的元素通过模拟全部出栈时，输出 
    remain--;//输出上限减一 
	for(auto x:path)cout<<x;
	cout<<endl;
	return;
}
if(stk.size())//说明可以进行出栈操作 
{//进行出栈操作
path.push_back(stk.top());//将栈顶元素暂时放入到向量中 
stk.pop(); //实际栈也进行出栈操作
dfs(u);//此时进入下一步操作的判断，这是下一步能入栈的操作 
stk.push(path.back());//当出栈操作模拟完之后实际栈和向量都要回复未出栈的状态以用来进行入栈操作 
path.pop_back();	
}
if(u<=n)
{//当可以进行入栈操作时
 stk.push(u);
 dfs(u+1);
 stk.pop();//这里我们在模拟完入栈操作之后还要将元素弹出，是因为当前栈是实际栈，我们在模拟完两步操作之后还要回复到初始状态 
	
 } 
	
}
int main()
{
	cin>>n;
	dfs(1);
	return 0;
}