https://www.acwing.com/problem/content/131/

今天这题，dfs爆搜

• dfs爆搜，注意20剪枝
• 所有火车都进栈出栈这代表一个结果产生
• 车站不为空就能选择出栈
• 如果还有火车未进栈，则可以选择进栈

cpp
#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

int n;  // 火车数量
vector<string> result;  // 存储所有可能的出栈顺序
stack<int> station;  // 模拟车站栈
vector<int> current;  // 当前出栈的火车顺序

// 深度优先搜索函数
void dfs(int inStack) {
    // 如果已经找到20种方案，停止搜索
    if (result.size() >= 20) {
        return;
    }

    // 如果所有火车都已进栈且栈为空，表示所有火车都已出栈
    if (inStack == n && station.empty()) {
        string s;
        // 将当前出栈顺序转换为字符串
        for (int v : current) {
            s += to_string(v);
        }
        // 将结果加入结果集
        result.push_back(s);
        return;
    }

    // 如果栈不为空，进行出栈操作
    if (!station.empty()) {
        int top = station.top();  // 获取栈顶元素
        station.pop();  // 出栈
        current.push_back(top);  // 将出栈的火车加入当前出栈顺序
        dfs(inStack);  // 递归调用dfs
        current.pop_back();  // 回溯，移除最后一个出栈的火车
        station.push(top);  // 将出栈的火车重新入栈
    }

    // 如果还有火车未进栈，进行进栈操作
    if (inStack < n) {
        station.push(inStack + 1);  // 将下一列火车进栈
        dfs(inStack + 1);  // 递归调用dfs
        station.pop();  // 回溯，移除最后一个进栈的火车
    }
}

int main() {
    cin >> n;  // 读取火车数量
    dfs(0);  // 调用dfs函数开始搜索

    // 输出前20种方案
    for (int i = 0; i < result.size() && i < 20; i++) {
        cout << result[i] << endl;
    }

    return 0;
}

然后最近在学习ruby

ruby
require 'set'

# 全局变量
$n = 0
$result = []
$station = []
$current = []

# 深度优先搜索
def dfs(in_stack)
  return if $result.size >= 20

  if in_stack == $n && $station.empty?
    # 所有火车都已出栈
    $result << $current.join
    return
  end

  if !$station.empty?
    # 出栈操作
    top = $station.pop
    $current << top
    dfs(in_stack)
    $current.pop
    $station.push(top)
  end

  if in_stack < $n
    # 进栈操作
    $station.push(in_stack + 1)
    dfs(in_stack + 1)
    $station.pop
  end
end

# 主函数
def main
  $n = gets.to_i
  dfs(0)

  # 按字典序排序
  $result.sort!

  # 输出前20种方案
  $result[0, 20].each { |r| puts r }
end

# 运行主函数
main