题解 | #火车进站#

解题思路：
1. 一个队列（待入站），一个栈（模拟火车站），一个列表（存放结果）
2. 深度优先搜索，遍历所有情况（两个方向，一个出站，一个入站）
结束递归条件（全部出站），保存结果
3. 对结果进行排序（普通冒泡排序会超时，可以用快排，或者在深搜时用插入排序）
4. 一个小细节，因为n<10, 可以把火车出站序列转为一个整数（用于排序比较）

# -*- coding: utf-8 -*-
# 开发者    : QSheng
# 代码文件  : HJ77 火车进站.py
# 创建时间  : 2021/7/28 9:07


class Solution:
    def __init__(self):
        self.rnt_ = list()      # 存放结果
        self.rnt_key_ = list()  # 存放结果的key

    def _add_rnt(self, tmp, tmp_key):
        """ 添加结果 （插排） """
        idx = -1
        for i in range(len(self.rnt_)-1, -1, -1):
            if tmp_key > self.rnt_key_[i]:
                idx = i
                break
        if idx == -1:
            self.rnt_ = [tmp] + self.rnt_
            self.rnt_key_ = [tmp_key] + self.rnt_key_
        else:
            self.rnt_ = self.rnt_[:idx+1] + [tmp] + self.rnt_[idx+1:]
            self.rnt_key_ = self.rnt_key_[:idx+1] + [tmp_key] + self.rnt_key_[idx+1:]


    def _dfs(self, n, station_stack, in_queue, out_stack):
        """
        深度优先搜索
        :param n:               火车数量
        :param station_stack:   车站
        :param in_queue:        火车入站序列
        :param out_stack:       火车出站序列
        :return:
        """
        # 两个方向，一个入站，一个出站

        # 出站
        if len(station_stack) > 0:
            station_stack_cp = station_stack.copy()
            out_stack_cp = out_stack.copy()

            train_tmp = station_stack_cp.pop()  # 出站
            out_stack_cp.append(train_tmp)      # 记录出站序列
            if len(out_stack_cp) == n:          # 全部已经出站
                # self.rnt_.append(out_stack_cp)
                # self.rnt_key_.append(int("".join(out_stack_cp)))
                # 直接插入排序
                self._add_rnt(out_stack_cp, int("".join(out_stack_cp)) )
                return
            self._dfs(n, station_stack_cp, in_queue, out_stack_cp)

        # 入站
        if len(in_queue) > 0:
            station_stack_cp = station_stack.copy()
            in_queue_cp = in_queue.copy()

            train_tmp = in_queue_cp.pop(0)      # 从入站队列中取出火车
            station_stack_cp.append(train_tmp)  # 入站
            self._dfs(n, station_stack_cp, in_queue_cp, out_stack)

        return

    def _compare(self, list_a, list_b):
        """ 比较 """
        for i in range(len(list_a)):
            if int(list_a[i]) != int(list_b[i]):
                return int(list_a[i]) - int(list_b[i])
        return 0

    def _compare2(self, indx_i, indx_j):
        """ 比较 """
        return self.rnt_key_[indx_i] - self.rnt_key_[indx_j]

    def _sort_rnt(self):
        """ 排序 """
        for i in range(1, len(self.rnt_)):
            for j in range(0, len(self.rnt_) - i):
                if self._compare2(j, j+1) > 0:
                    self.rnt_[j], self.rnt_[j + 1] = self.rnt_[j + 1], self.rnt_[j]
                    self.rnt_key_[j], self.rnt_key_[j + 1] = self.rnt_key_[j + 1], self.rnt_key_[j]

    def solve(self, n, arr):

        self._dfs(n, list(), arr, list())  # 深度优先搜索
        # self._sort_rnt()                   # 排序（会超时，改为一边搜索，一边排序）
        rnt = ""
        for i in range(len(self.rnt_)-1):
            rnt += "{}\n".format(" ".join(self.rnt_[i]))
        rnt += "{}".format(" ".join(self.rnt_[-1]))

        return rnt

import sys
if __name__ == '__main__':
    is_IDE = False
    if is_IDE:
        fr = open("data/HJ77.txt", "r", encoding="utf-8")
    else:
        fr = sys.stdin

    while True:
        line_n = fr.readline().strip()
        if line_n == "":
            break
        line_list = fr.readline().strip().split(" ")
        print(Solution().solve(int(line_n), line_list))

    if is_IDE:
        fr.close()