火车进站

Posted on

题目描述

1
给定一个正整数N代表火车数量，0<N<10，接下来输入火车入站的序列，一共N辆火车，每辆火车以数字1-9编号，火车站只有一个方向进出，同时停靠在火车站的列车中，只有后进站的出站了，先进站的才能出站。要求以字典序排序输出火车出站的序列号。

输入描述

1
有多组测试用例，每一组第一行输入一个正整数N（0<N<10），第二行包括N个正整数，范围为1到9。

输出描述

1
输出以字典序从小到大排序的火车出站序列号，每个编号以空格隔开，每个输出序列换行，具体见sample。

示例

输入

1
2
3
1 2 3

输出

1
2
3
4
5
1 2 3
1 3 2
2 1 3
2 3 1
3 2 1

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
package main

import (
	"fmt"
	"sort"
	"strings"
)

type stack []string

func (s *stack) push(v string) {
	*s = append(*s, v)
}

func (s *stack) pop() string {
	l := len(*s)
	result := (*s)[l-1]
	*s = (*s)[0 : l-1]
	return result
}

func (s *stack) unshift() string {
	result := (*s)[0]
	*s = (*s)[1:]
	return result
}

func (s *stack) empty() bool {
	return len(*s) == 0
}

func main() {
	for {
		var N uint8
		_, err := fmt.Scan(&N)
		if err != nil {
			break
		}

		var trainList = make([]string, 0, N)
		for i := uint8(0); i < N; i++ {
			var train string
			fmt.Scan(&train)
			trainList = append(trainList, train)
		}

		pre := stack(trainList)
		in := stack{}
		out := stack{}
		handle(pre, in, out)
	}

	sort.Strings(results)
	for _, result := range results {
		fmt.Println(result)
	}
}

var (
	results []string
)

func handle(pre, in, out stack) {
	if pre.empty() && in.empty() {
		results = append(results, strings.Join(out, " "))
		return
	}

	if !pre.empty() {
		prec := make([]string, len(pre))
		inc := make([]string, len(in))
		outc := make([]string, len(out))

		copy(prec, pre)
		copy(inc, in)
		copy(outc, out)

		pres := stack(prec)
		ins := stack(inc)
		outs := stack(outc)

		ins.push(pres.unshift())
		handle(pres, ins, outs)
	}

	if !in.empty() {
		prec := make([]string, len(pre))
		inc := make([]string, len(in))
		outc := make([]string, len(out))

		copy(prec, pre)
		copy(inc, in)
		copy(outc, out)

		pres := stack(prec)
		ins := stack(inc)
		outs := stack(outc)

		outs.push(ins.pop())
		handle(pres, ins, outs)
	}
}