题解 | #火车进站#

#include <stdio.h>
#include <string.h>
struct stack{
    char num[10];
    int top;
};

void add(char n,struct stack *sta){
    sta->num[++(sta->top)]=n;
}

char pop(struct stack *sta){
    char te;
    te=sta->num[sta->top];
    sta->top--;
    return te;
}

struct stack train1,train2;
int m=0;
char strain[20];
char strai[10000][20];
void dfs(int n){
    char tin,tout;
    if((train1.top==-1)&&(train2.top==-1)) {
        
        
        memcpy(strai[m], strain,n);
  
        m++;
   
        return;
    }
    if((train1.top!=-1)){
        if(train2.top==-1) {
            tin=pop(&train1);
            add(tin,&train2);
            dfs(n);
            add(tin,&train1);
            pop(&train2);
       
        }
        else{
            tout=pop(&train2);
            strain[n]=tout;
            dfs(n+1);
            add(tout,&train2);
            tin=pop(&train1);
            add(tin,&train2);
            dfs(n);
            pop(&train2);
            add(tin,&train1);
          
        }
    }
    else {
        tout=pop(&train2);
        strain[n]=tout;
        dfs(n+1); 
        add(tout,&train2);
    }
    return;
}

int main(){
    int i,j,n;
    char str[10],temp[10];
    
    while(scanf("%d",&n)!=-1){
        train1.top=-1;
        train2.top=-1;
        m=0;
        for(i=0;i<n;i++){
            scanf("%s",str+i);
            add(str[i],&train2);
        }
        for(i=0;i<n;i++) add(pop(&train2),&train1);
       memset(strai, '\0', 20000);
        dfs(0);

        for(i=0;i<m-1;i++){
            for(j=0;j<m-1-i;j++){
                if(strcmp(strai[j],strai[j+1])>0){
                    memcpy(temp, strai[j],n);
                    memcpy(strai[j], strai[j+1],n);
                    memcpy(strai[j+1], temp,n);
                }
            }
        }
        for(i=0;i<m;i++){
            for(j=0;j<n;j++) printf("%c ",strai[i][j]);
            printf("\n");
        }
    }
    return 0;
}