7 - 2 열 객차 스케줄 링 (25 point (s)) (창고 의 고전 제목)

3174 단어 데이터 구조
7 - 2 열 객차 스케줄 링 (25 point (s))
        1  ======       

여러분 은 아마도 일부 데이터 구조 교재 에서 '객차 배치 문제' 를 본 적 이 있 을 것 입 니 다.오늘 우 리 는 아래 칸 의 배 치 를 실제 적 으로 조작 할 것 이다.위의 ASCII 문자 그림 을 대조 하면 문제 설명 은 다음 과 같 습 니 다.
세 개의 평행 열차 궤도 (1, 2, 3) 와 1 - 3 과 2 - 3 두 개의 연결 궤도 가 있다.기 존의 한 칸 은 1 번 궤도 에 멈 춰 있 으 니 두 개의 연결 궤도 와 3 번 궤 도 를 이용 하여 원 하 는 순서에 따라 2 번 궤도 로 옮 겨 주 십시오.규칙 은:
차 한 칸 씩 옮 기기;
4. 567917. 1 번 궤도 에 있 는 칸 은 1 - 3 연결 도 를 거 쳐 3 번 궤도 에 들 어가 거나 (이 조작 은 '1 - > 3' 으로 기록) 두 개의 연결 궤 도 를 거 쳐 2 번 궤도 에 직접 들 어가 거나 (이 조작 은 '1 - > 2' 로 기록)
4. 567917. 일단 객차 가 2 번 궤도 에 들 어가 면 이 궤 도 를 다시 옮 길 수 없다
4. 567917. 3 번 궤도 에 있 는 칸 은 2 - 3 연결 도 를 거 쳐 2 번 궤도 에 들 어 갈 수 밖 에 없다 (이 조작 은 '3 - > 2' 로 기록 된다)
4. 567917. 분명히 그 어떠한 차량 도 다른 칸 을 지나 가 거나 건 너 거나 돌아 이동 할 수 없다
주어진 1 번 주차 순서 에 대해 스케줄 링 을 통 해 2 번 궤도 가 요구 하 는 순 서 를 실현 할 수 있다 면 조작 서열 을 제시한다.만약 안 된다 면, 사용자 Are (당신) you (예) kidding (케 이 딩) me (입 니까?
입력 형식:
두 줄 은 대문자 로 구 성 된 비 어 있 는 문자열 로 첫 줄 은 1 번 궤도 에 주 차 된 칸 의 왼쪽 에서 오른쪽으로 의 순 서 를 나타 내 고, 두 번 째 줄 은 2 번 궤도 에 주 차 를 요구 하 는 진입 순 서 를 나타 낸다.두 줄 의 문자열 은 길이 가 같 고 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?

code:
#include 
#include 
struct node{
    int x,y;
}ans[30];//        
int main(){
    char s1[30];//  1
    char s2[30];//  2
    char s3[30];//  3
    int top1,top2,top3,cnt;
    top1 = 0;
    top2 = 0;//  top12            
    top3 = -1;//          ,   -1  
    cnt = 0;
    gets(s1);
    gets(s2);
    int len = strlen(s1)-1;
    while(top1<=len){//        
        if(s1[top1]==s2[top2]){//    1,2  ,    1     2,        
            ans[cnt].x = 1;
            ans[cnt++].y = 2;
            top1++;
            top2++;
        }
        else if(top3!=-1&&s3[top3]==s2[top2]){//   3           2     ,    3   2
            ans[cnt].x = 3;
            ans[cnt++].y = 2;
            top2++;
            top3--;
        }
        else{//         3, 1 3
            ans[cnt].x = 1;
            ans[cnt++].y = 3;
            s3[++top3] = s1[top1++];
        }
    }
    //      3   ,      2,             2    
    int flag = 1;
    while(top3!=-1){
        if(s3[top3]!=s2[top2]){
            flag = 0;
            break;
        }
        else{
            top3--;
            top2++;
            ans[cnt].x = 3;
            ans[cnt++].y = 2;
        }
    }
    int i;
    if(flag){
        for(i = 0; i < cnt; i++){
            printf("%d->%d
",ans[i].x,ans[i].y); } } else printf("Are you kidding me?
"); return 0; }

좋은 웹페이지 즐겨찾기