1 ====== <--移動方向
/
3 =====
\
2 ====== -->移動方向
大家或許在某些資料結構教材上見到過“列車廂調度問題”（當然沒見過也不要緊）。今天，我們就來實際操作一下列車廂的調度。對照上方的ASCII字符圖，問題描述如下：
有三條平行的列車軌道（1、2、3）以及1-3和2-3兩段連接軌道。現有一列車廂停在1號軌道上，請利用兩條連接軌道以及3號軌道，將車廂按照要求的順序轉移到2號軌道。規則是：
每次轉移1節車廂；
處在1號軌道的車廂要么經過1-3連接道進入3號軌道（該操作記為"1->3"），要么經過兩條連接軌道直接進入2號軌道（該操作記為"1->2"）；
一旦車廂進入2號軌道，就不可以再移出該軌道；
處在3號軌道的車廂，只能經過2-3連接道進入2號軌道（該操作記為"3->2"）；
顯然，任何車廂不能穿過、跨越或繞過其它車廂進行移動。
對于給定的1號停車順序，如果經過調度能夠實作2號軌道要求的順序，則給出操作序列；如果不能，就反問用戶 Are(你) you(是) kidding(凱丁) me(么)?
輸入格式:
兩行由大寫字母組成的非空字串，第一行表示停在1號軌道上的車廂從左到右的順序，第二行表示要求車廂停到2號軌道的進道順序（輸入樣例1中第二行CBA表示車廂在2號軌道的停放從左到右是ABC，因為C最先進入，所以在最右邊）。兩行字串長度相同且不超過26（因為只有26個大寫字母），每個字母表示一節車廂。題目保證同一行內的字母不重復且兩行的字母集相同。
輸出格式:
如果能夠成功調度，給出最短的操作序列，每個操作占一行。所謂“最短”，即如果1->2可以完成的調度，就不要通過1->3和3->2來實作。如果不能調度，輸出 "Are you kidding me?"
輸入樣例1:
ABC
CBA
輸出樣例1:
1->3
1->3
1->2
3->2
3->2
輸入樣例2:
ABC
CAB
輸出樣例2:
Are you kidding me?
代碼：
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAX 100
#define LEN sizeof(StackNode)
typedef struct CH
{
char ch;
struct CH *next;
}StackNode;
typedef struct
{
StackNode *top;
}Stacktop;
int DY(Stacktop *S);
void Push(Stacktop *S,char a);
void Pop(Stacktop *S);
int Empty(Stacktop *S);
char read(Stacktop *S);
int main()
{
Stacktop *S=(Stacktop*)malloc(sizeof(Stacktop)); //請你一定一定不要忘記初始化！！！！
S->top=NULL;
DY(S);
return 0;
}
int DY(Stacktop *S)
{
Stacktop *list1=(Stacktop*)malloc(sizeof(Stacktop));
Stacktop *list2=(Stacktop*)malloc(sizeof(Stacktop));
char a[MAX],b[MAX];
int i=0,j,x;
int po[MAX];
list1->top=NULL;
list2->top=NULL;
scanf("%s",a);
scanf("%s",b);
x=strlen(a)-1;
j=0;//strlen(b)-1;
while(a[i])
{
if(i<x)
{
Push(S,a[i]);
po[i]=13;
}
else if(i==x)
{
Push(list1,a[i]);
po[i]=12;
//printf("list:%c\n",read(list1));
if(b[j++]!=read(list1)){printf("Are you kidding me?\n");return 0;}
}
i++;
}
while(S->top!=NULL)
{
Push(list1,read(S));
if(b[j++]!=read(list1)){printf("Are you kidding me?\n");return 0;}
//printf("list:%c\n",read(list1));
Pop(S);
po[i]=32;
i++;
}
for(x=0;x<i;x++)
{
printf("%d->%d\n",po[x]/10,po[x]%10);
}
return 1;
}
int Empty(Stacktop *S)//是否空堆疊
{
return S->top==NULL;
}
void Push(Stacktop *S,char a) //入堆疊
{
StackNode *p=(StackNode*)malloc(LEN);
p->ch=a;
p->next=S->top;
S->top=p;
}
char read(Stacktop *S) //讀取
{
return S->top->ch;
}
void Pop(Stacktop *S) //出堆疊
{
StackNode *p=S->top;
if (S->top!=NULL){
S->top=p->next;
free(p);}
}
救救孩子吧
uj5u.com熱心網友回復：
S相當于3號軌道，list1相當于2號軌道，當輸入的字串只剩一個字符是進入2號軌道，再把所有的3號軌道的字符加入2號軌道，只要有進入2號軌道就判斷輸入的第二個字串的第j個字符是否一樣，不一樣就代表不能調度，為啥有一個PTA測驗點死活過不去uj5u.com熱心網友回復：
方便把題目鏈接發一下嘛，我驗證一下我的想法uj5u.com熱心網友回復：
https://pintia.cn/problem-sets/1239445850577838080/problems/1239707569174749184uj5u.com熱心網友回復：
發在樓上了
uj5u.com熱心網友回復：
救救孩子吧，這點不過我真的好不甘心
uj5u.com熱心網友回復：
無操作權限，這是你們的作業吧？uj5u.com熱心網友回復：
是的..
uj5u.com熱心網友回復：
現在也快結束了，不過我還是不知道我的代碼為什么不行
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/104456.html
標籤：C語言
上一篇：c語言如何判斷某一天是否為生日？