[PAT] [Data Structure] Training

By Data Structure

< p style="margin-top:0px; margin-bottom:0px; padding-top:0px; padding-bottom:0px; text-align:right">
Contents ( ?)[+]

1 ====== <---moving direction / 3 == === \ 2 ====== -->Movement direction

You may have seen ” Train dispatching problem” (Of course it doesn’t matter if you haven’t seen it before). Today, we will actually operate the dispatch of train cars. Compared with the ASCII character image above, the problem is described as follows:

There are three parallel train tracks (1, 2, 3) and 1 -3 and 2-3 two connecting tracks. There is currently a train car parked on No. 1 track. Please use the two connecting tracks and No. 3 track to transfer the carriages to No. 2 track in the required order. The rule is:

  • 1 car per transfer;
  • The car on track 1 will either enter track 3 through the 1-3 link (this operation is marked as “1->3”), or directly enter track 2 through the two connecting tracks ( This operation is recorded as “1->2”);
  • Once the carriage enters the No. 2 track, it cannot be moved out of the track;

    • < li style="margin:0px; padding:0px">Cars on track 3 can only enter track 2 through the 2-3 junction (this operation is recorded as “3->2”);

  • Obviously, no carriage can move through, cross or bypass other carriages.

For a given parking sequence of No. 1, if the sequence required by track No. 2 can be achieved after scheduling, then Give the sequence of operations; if not, just ask the user Are(you) you(yes) kidding(凯丁) me(what)?

Input format:

< p style="margin-top:0.5em; margin-bottom:0.5em; padding-top:0px; padding-bottom:0px; color:rgb(51,51,51); font-family:"Microsoft YaHei", helvetica,sans-serif; font-size:14px; line-height:21px"> Two lines of non-empty strings composed of uppercase letters, the first line represents the order from left to right of the carriages parked on track 1, The second line indicates the entry order that requires the car to stop to track No. 2 (input the second line in Example 1 CBA means the carriage is in The parking of track 2 from left to right is ABC, because C is the first to enter, so it is on the far right). The length of the two lines of strings is the same and does not exceed 26 (because there are only 26 uppercase letters), and each letter represents a carriage. The title guarantees that the letters in the same line are not repeated and that the letter sets of the two lines are the same.

Output format:

If it can be scheduled successfully, give the shortest operation Sequence, each operation occupies one line. The so-called “shortest”, that is, if 1->2 can complete the scheduling, do not use 1->3 and 3->2 to achieve. If it cannot be scheduled, output “Are you kidding me?”

Input example 1:

ABCCBA

Output sample 1: 

1->31->31 ->23->23->2

Input example 2:

ABCCAB

Output sample 2:

Are you kidding me?

[cpp] view plain copy

print? View code piece on CODE Derived to my code piece

  1. #include “iostream” li>
  2. #include “stack”
  3. #include “vector”
  4. #include “cstring”
  5. usingnamespacestd;
  6. vector<int>v; li>
  7. stack<char> s1,s2,s3;
  8. int main()
  9. {
  10. intflag=1;
  11. char astr[100],bstr[100];
  12. scanf(“%s”,astr);scanf(“%s”,bstr);
  13. for(inti=strlen(astr)-1;i>=0;i–)
  14. {
  15. s1.push(astr[i]);
  17. for(inti=strlen(bstr)-1 ;i>=0;i–)
  18. {
  19. s2.push(bstr[i]);
  22. while< span style="margin:0px; padding:0px; border:none; background-color:inherit">(!s2.empty())
  23. {
  25. if(!s1.empty())
  26. {
  27. if(s1.top()==s2.top())
  28. {}
  29. v.push_back(1);
  30. s1.pop(); s1.pop();
  31. s2.pop();
  32. // break;
  34. elseif(!s3.empty()&& s2.top()==s3 .top())
  35. {
  36. < span style="margin:0px; padding:0px; border:none; color:black; background-color:inherit">v.push_back(3);
  37. s2.pop();
  38. s3.pop();
  39. //break;
  41.             else   
  42.             {    
  43.                 v.push_back(2);    
  44.                 s 3.push(s1.top());    
  45.                 s1.pop();    
  46.                     
  47.             }    
  48.         }    
  49.             
  50.         else    
  51.         {    
  52.                 
  53.             if(s2.top()!=s3.top())    
  54.             {    
  55.                 flag=0;    
  56.                // break;    
  57.             }    
  58.             else    
  59.             {    
  60.                 v.push_back(3);    
  61.                 s2.pop();    
  62.                 s3.pop();  
  63.                // break;   
  64.             }    
  65.         }    
  66.             
  67.     }    
  68.         
  69.     if(flag)    
  70.     {    
  71.         for(int b:v)    
  72.         {    
  73.             if(b==1)    
  74.             {    
  75.                 printf(“1->2\n”);  
  76.             }    
  77.             else if(b==2)    
  78.             {    
  79.                 printf(“1->3\n”);    
  80.             }    
  81.             else if(b==3)  
  82.             {    
  83.                 printf(“3->2\n”);   
  84.             }    
  85.         }    
  86.     }    
  87.     else    
  88.     {    
  89.          printf(“Are you kidding me?\n”, );     
  90.     }    
  91.     return 0;    
  92. }  


目录(?)[+]

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:

ABCCBA

输出样例1:

1->31->31->23->23->2

输入样例2:

ABCCAB

输出样例2:

Are you kidding me?

[cpp]  view plain  copy

 print ? 在CODE上查看代码片 派生到我的代码片

  1. #includ e “iostream”      
  2. #include “stack”  
  3. #include “vector”  
  4. #include “cstring”  
  5. using namespace std;     
  6. vector<int> v;  
  7. stack<char> s1,s2,s3;     
  8. int main()    
  9. {    
  10.     int  flag=1;  
  11.     char astr[100],bstr[100];  
  12.     scanf(“%s”,astr);scanf(“%s”,bstr);   
  13.     for(int i=strlen(astr)-1;i>=0;i–)    
  14.     {    
  15.         s1.push(astr[i]);    
  16.     }    
  17.     for(int i=strlen(bstr)-1;i>=0;i–)    
  18.     {    
  19.         s2.push(bstr[i]);    
  20.     }  
  21.   
  22.     while(!s2.empty())      
  23.     {    
  24.             
  25.         if(!s1.empty())    
  26.         {    
  27.             if(s1.top()==s2.top())    
  28.             {    
  29.                 v.push_back(1);    
  30.                 s1.pop();    
  31.                 s2.pop();    
  32.                // break;  
  33.             }    
  34.             else if(!s3.empty() && s2.top()==s3.top())  
  35.             {  
  36.                 v.push_back(3);  
  37.                 s2.pop();  
  38.                 s3.pop();  
  39.                // break;  
  40.             }  
  41.             else  
  42.             {    
  43.                 v.push_back(2);    
  44.                 s3.push(s1.top());    
  45.                 s1.pop();    
  46.                     
  47.             }    
  48.         }    
  49.             
  50.         else    
  51.         {    
  52.                 
  53.             if(s2.top()!=s3.top())    
  54.             {    
  55.                 flag=0;    
  56.                // break;    
  57.             }    
  58.             else    
  59.             {    
  60.                 v.push_back(3);    
  61.                 s2.pop();    
  62.                 s3.pop();  
  63.                // break;   
  64.             }    
  65.         }    
  66.             
  67.     }    
  68.         
  69.     if(flag)    
  70.     {    
  71.         for(int b:v)    
  72.         {    
  73.             if(b==1)    
  74.             {    
  75.                 printf(“1->2\n”);  
  76.             }    
  77.             else if(b==2)    
  78.             {    
  79.                 printf(“1->3\n”);    
  80.             }    
  81.             else if(b==3)  
  82.             {    
  83.                 printf(“3->2\n”);   
  84.             }    
  85. < span style="margin:0px; padding:0px; border:none; color:black; background-color:inherit">        }    
  86.     }    
  87.     else    
  88.     {    
  89.          printf(“Are you kidding me?\n”, );     
  90.     }    
  91.     return 0;    
  92. }  

[cpp]  view plain  copy

 print ? 在CODE上查看代码片 派生到我的代码片

  1. #include “iostream”      
  2. #include “stack”  
  3. #include “vector”  
  4. #include “cstring”  
  5. using namespace std;     
  6. vector<int> v;  
  7. stack<char> s1,s2,s3;     
  8. int main()    
  9. {    
  10.     int  flag=1;  
  11.     char astr[100],bstr[100];  
  12.     scanf(“%s”,astr);scanf(“%s”,bstr);   
  13.     for(int i=strlen(astr)-1;i>=0;i–)    
  14.     {    
  15.         s1.push(astr[i]);    
  16.     }    
  17.     for(int i=strlen(bstr)-1;i>=0;i–)    
  18.     {    
  19.         s2.push(bstr[i]);    
  20.     }  
  21.   
  22.     while(!s2.empty())      
  23.     {    
  24.             
  25.         if(!s1.empty())    
  26.         {    
  27.             if(s1.top()==s2.top())    < /span>
  28.             {    
  29.                 v.push_back(1);    
  30.                 s1.pop();    
  31.                 s2.pop();    
  32.                // break;  
  33.             }    
  34.             else if(!s3.empty() && s2.top()==s3.top())  
  35.             {  
  36.                 v.push_back(3);  
  37.                 s2.pop();  
  38.                 s3.pop();  
  39.                // break;  
  40.             }  
  41.             else  
  42.             {    
  43.                 v.push_back(2);    
  44.                 s3.push(s1.top());    
  45.                 s1.pop();    
  46.                     
  47.             }    
  48.         }    
  49.             
  50.         else    
  51.         {    
  52.                 
  53.             if(s2.top()!=s3.top())    
  54.             {    
  55.                 flag=0;    
  56.                // break;    
  57.             }    
  58.             else    
  59.             {    
  60.                 v.push_back(3);    
  61.                 s2.pop();    
  62.                 s3.pop();  
  63.                // break;   
  64.             }    
  65.         }    
  66.             
  67.     }    
  68.         
  69.     if(flag)    
  70.     {    
  71.         for(int b:v)    
  72.         {    
  73.             if(b==1)    
  74.             {    
  75.                 printf(“1->2\n”);  
  76.             }    
  77.             else if(b==2)    
  78.             {    
  79.                 printf(“1->3\n”);    
  80.             }    
  81.             else if(b==3)  
  82.             {    
  83.                 printf(“3->2\n”);   
  84.             }    
  85.         }    
  86.     }    
  87.     else    
  88.     {    
  89.          printf(“Are you kidding me?\n”, );     
  90.     }    
  91.     return 0;    
  92. }  

[cpp]  view plain  copy

 print ? 在CODE上查看代码片 派生到我的代码片

[cpp]  view plain  copy

 print ? 在CODE上查看代码片 派生到我的代码片

, , , ,

Leave a Comment

Your email address will not be published.