AcWing 火车进栈

Description

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

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

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

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

Input

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

Output

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

Data Size

• 1≤n≤20

Sample Input

3

Sample Output

123132213231321

题解：

• 搜索（用栈模拟）。
• 如果一上去题都不看就是无脑爆搜那就直接WA了（我就是这样）
• 注意，这个搜索是基于“栈“的性质的！
• 所以面对每一个状态，有下列两种选择：
  1. 把下一个数进栈
  2. 将栈顶弹出
• 那么经过2 * n次操作后，所以元素肯定都已经出栈了。

#include 
    
     #include 
     
      #include 
      
       #define N 25using namespace std;int n, flag, cnt;int a[N];stack
       
         stk;void dfs(int step, int num){    if(flag) return;    if(step > 2 * n)    {        cnt++;        if(cnt == 20) flag = 1;        for(int i = 1; i <= 2 * n; i++)            if(a[i]) cout << a[i];        cout << endl;        return;    }    if(stk.size())    {        int t =stk.top();        a[step] = t;        stk.pop();        dfs(step + 1, num);        stk.push(t);        a[step] = 0;    }    if(num <= n)    {        stk.push(num);        dfs(step + 1, num + 1);        stk.pop();    }}int main(){    cin >> n;    dfs(1, 1);    return 0;}