火车进栈

GitHub跳转原题关系图返回列表

DFS 按「先出栈、后进栈」分支天然按字典序枚举出站序列，收满前 20 个立即整树剪枝。

OJ: roj

题目 ID: 3030

难度:普及-

标签:栈dfspython

创建: 2026-10-01 11:03

更新: 2026-10-07 13:50

前置题目
roj 1354括弧匹配检验A 教的“栈空弹栈即非法”这一括号合法性失败点，正是 B 第一步把火车进出站归约为合法括号序列时所用的“栈不能空着出”约束（代码用 if stack 保证不空弹），B 在此合法性骨架上再叠加字典序 DFS 枚举与前 20 整树剪枝。leetcodecn valid-parentheses有效的括号B 的第一步直接沿用 A 教的括号合法性判定（栈空不能出栈），把火车进出站序列归约为合法括号序列结构，再在其上叠加字典序 DFS 枚举与剪枝。luogu P1739表达式括号匹配B 的第一步把火车进出站操作序列翻译成合法括号结构，直接复用 A 教的「扫描中 balance 不能为负」这一前缀非负判定，再叠加 A 未教的 DFS 按「先出栈后进栈」字典序枚举与收满 20 个整树剪枝。

目录

  1. 题目描述
  2. 思路
  3. 参考代码

题目描述

nn 列火车按 1∼n1\sim n 的顺序依次进站，车站是一个栈。每次可以选择让下一列火车进栈，或让栈顶火车出站。按字典序输出前 20 种可能的出站序列，每行一种、无空格。1≤n≤201\le n\le 20。

样例输入 3，输出 123、132、213、231、321。

思路

每个状态优先尝试「出栈」再「进栈」，DFS 到达叶子的顺序就是出站序列的字典序；收满 20 个后立即剪枝返回。

参考代码

Python 版：

python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-01 11:03
# update_at: 2026-10-01 11:03

import sys

LIMIT = 20  # 题面只要求前 20 种方案，凑够即可整体剪枝

n: int = 0              # 火车数量
ans: list[str] = []     # 收集到的出栈序列：每个状态先试「出栈」再试「进栈」，产出天然按字典序


def dfs(next_in: int, stack: list[int], out: list[int]) -> None:
    """从当前（下一节进站编号, 栈, 已出站序列）出发，枚举所有出栈序列。"""
    if len(ans) == LIMIT:
        return                          # 前 20 个已收集完毕，其余分支全部放弃
    if len(out) == n:
        ans.append(''.join(map(str, out)))
        return
    if stack:                           # 分支一：栈顶火车出站——能让出站序列更小，优先走
        out.append(stack.pop())
        dfs(next_in, stack, out)
        stack.append(out.pop())         # 回溯：复原栈与出站序列
    if next_in <= n:                    # 分支二：右侧下一节火车进站
        stack.append(next_in)
        dfs(next_in + 1, stack, out)
        stack.pop()


def solve() -> None:
    global n
    n = int(sys.stdin.read())
    dfs(1, [], [])
    print('\n'.join(ans))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 11:20
 * update_at: 2026-10-06 11:20
 */

#include <cstdio>
using namespace std;

typedef long long ll;

const int LIMIT = 20;   // 只输出前 20 个
const int MAXN = 25;    // n <= 20

int n;                  // 火车数量
int ans_cnt;            // 已收集的出站序列数
int stk[MAXN];          // 手动栈，stk[1..top]
int top;                // 栈顶指针
int out_seq[MAXN];      // 已出站序列，out_seq[1..out_cnt]
int out_cnt;            // 已出站数量

// 从当前状态出发 DFS，优先「出栈」再「进栈」，天然按字典序
void dfs(int next_in) {
    if (ans_cnt == LIMIT) return;           // 收满 20 个，整树剪枝
    if (out_cnt == n) {                     // 全部出站，得到一个合法序列
        for (int i = 1; i <= n; ++i)
            printf("%d", out_seq[i]);
        printf("\n");
        ++ans_cnt;
        return;
    }
    // 分支一：栈顶出站，能让当前出站序列更小，优先走
    if (top > 0) {
        out_seq[++out_cnt] = stk[top--];
        dfs(next_in);
        stk[++top] = out_seq[out_cnt--];    // 回溯
    }
    // 分支二：下一节火车进站
    if (next_in <= n) {
        stk[++top] = next_in;
        dfs(next_in + 1);
        --top;                              // 回溯
    }
}

int main() {
    scanf("%d", &n);
    dfs(1);
    return 0;
}