题解 | #火车进站#

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

static int sortSeq(const void *a, const void *b)
{
    return strcmp((char *)a, (char *)b);
}

static char g_stack[3][11] = {0}; /* 0,1,2 分别对应未入火车站的火车队列，在火车站中的火车队列，以及出栈后的火车队列 */
static char g_seq[5000][11] = {0};
static int g_num, g_kind = 0;
static void HandleSeq(char idx0, char idx1, char idx2, char in)
{
    if (in) { /* 不为 0 表示进入火车站 */
        if (idx0 >= g_num) return;
        g_stack[1][++idx1] = g_stack[0][idx0++];
        HandleSeq(idx0, idx1, idx2, 0);
        g_stack[1][idx1] = g_stack[0][idx0 - 1];
        HandleSeq(idx0, idx1, idx2, 1);
    } else { /* 当前最后入火车站的火车出战 */
        if (idx2 >= g_num) { strcpy(g_seq[g_kind++], g_stack[2]); return; }
        if (idx1 < 0) return;
        g_stack[2][idx2++] = g_stack[1][idx1--];
        HandleSeq(idx0, idx1, idx2, 0);
        HandleSeq(idx0, idx1, idx2, 1);
        g_stack[1][idx1 + 1] = g_stack[2][idx2 - 1];
    }
}

int main(int argc, char** argv)
{
    scanf("%d", &g_num);
    for (int i = 0; i < g_num; i++) scanf("%hhd", &g_stack[0][i]);
    HandleSeq(0, -1, 0, 1);
    qsort(g_seq, g_kind, sizeof(g_seq[0]), sortSeq);
    for (int i = 0; i < g_kind; i++) {for (int j = 0; j < g_num; j++) {printf("%d ", g_seq[i][j]);} printf("\n");}
    return 0;
}