题解 | #火车进站#

#include <stdio.h>
#include <string.h>
int kind = 0;
void DFS(int stack[], int list[][10], int train[], int n, int index, int pos, int top);
int combine(int a[10], int b[10], int n);

int main()
{
  int n;

  while (scanf("%d", &n) != EOF)
  {
    int train[n];
    for (int i = 0; i < n; i++)
    {
      scanf("%d", &train[i]);
    }

    int list[10000][10];
    int stack[n];
    int top = -1;

    DFS(stack, list, train, n, 1, 0, top);
    // list[kind][n]排序
    //  递增排序,冒泡
    int flag, temp;
    for (int j = kind; j >= 2; j--)
    {
      flag = 0;
      for (int i = 1; i < j; i++)
      {
        if (combine(list[i], list[i + 1], n) == 1)
        {
          for (int k = 0; k < n; k++)
          {
            temp = list[i][k];
            list[i][k] = list[i + 1][k];
            list[i + 1][k] = temp;
          }
          flag = 1;
        }
      }
      if (flag == 0)
        break;
    }
    for (int i = 1; i <= kind; i++)
    {
      for (int j = 0; j < n; j++)
      {
        printf("%d ", list[i][j]);
      }
      printf("\n");
    }
  }

  return 0;
}

//index 入栈车序号,pos当前序列 记录位置 top栈顶
//C如果不公共变量涉及回溯时需要传入的变量太多了

void DFS(int stack[], int list[][10], int train[], int n, int index, int pos, int top)
{
  if (pos == n)
  {
    kind++;
    for(int i=0;i<n;i++){
      list[kind][i]=list[0][i];
    }
    
 
    return;
  }

  for (int j = 0; j < 2; j++)
  {
    if (j == 0 && top >= 0)
    {
      //出栈
      int temp = stack[top];
      list[0][pos] = stack[top--];
      DFS(stack, list, train, n, index, pos + 1, top);
      stack[++top] = temp;
    }

    //入栈
    if (j == 1 && index <= n)
    {
      stack[++top] = train[index - 1];
      index++;
      DFS(stack, list, train, n, index, pos, top);
      index--;
      top--;
    }
  }
}

int combine(int a[10], int b[10], int n)
{
  int ret=0;
  int i=0;
  while(a[i]==b[i]){
    i++;
  }
  if(a[i]>b[i])
  ret = 1;
  
  return ret;
}