题解 | #火车进站#

#include<stdio.h>
int N, size;
int ans[4862][10];
int wait[10];
int in[10];
int out[10];
int topi, topw, outi;

void dfs() {
    if (outi == N) {
        for (int i = 0; i < N; i++) 
            ans[size][i] = out[i];
        size++;
        return;
    }
    else {
        if (topi >= 0) {
            int tempin = in[topi];
            out[outi++] = in[topi--];
            dfs();
            outi--, topi++;
            in[topi] = tempin;
        }
        if (topw >= 0) {
            in[++topi] = wait[topw--];
            dfs();
            topi--;
            topw++;
        }
    }
}

int main() {
    int n;
    while (~scanf("%d", &n)) {
        N = n;
        size = 0;
        for (int i = n-1; i>=0; i--) {
            scanf("%d", wait + i);
            in[i] = out[i] = 0;
        }
            
        topi = -1;
        topw = n - 1;
        outi = 0;

        dfs();

        for (int i = 0; i < size; i++)
            for (int j = 0; j + 1 < size - i; j++) {
                int k = 0;
                while (ans[j][k] == ans[j + 1][k])k++;
                if (ans[j][k] > ans[j + 1][k]) 
                    while (k < N) {
                        int t = ans[j][k];
                        ans[j][k] = ans[j+1][k];
                        ans[j+1][k] = t;
                        k++;
                    }
                
            }

        for (int i = 0; i < size; i++) {
            for (int j = 0; j < N; j++)
                printf("%d ", ans[i][j]);
            printf("\n");
        }
    }
}