7 - 11 칸 예약 (25 분) (스 택)

 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
#include
#include
#include
using namespace std;
int xu[30];
int main()
{
    stack<char>s1,s2,s3;

    int k=0;
    char a[30],b[30];
    int i;
    gets(a);
    gets(b);
    int len1 = strlen(a);
    int len2 = strlen(b);
    for(i=len1-1; i >= 0; i--)
    {
        s1.push(a[i]);
    }

    for(i=len2-1; i >= 0; i--)
    {
        s2.push(b[i]);
    }
    int flag = 0;
    while(!s2.empty())
    {
        if(!s1.empty()&&s1.top() == s2.top())
        {
            s1.pop();
            s2.pop();
            xu[k++] = 1;//1->2
        }
        else if(!s3.empty()&&s3.top()==s2.top())
        {
            s3.pop();
            s2.pop();
            xu[k++] = 3;//3->2
        }
        else if(s1.empty()&&!s2.empty()&&s3.top()!=s2.top())
        {
            flag = 1;
            break;
        }
        else
        {
            s3.push(s1.top());
            s1.pop();
            xu[k++] = 2;//1->3
        }
    }
    if(flag)
        printf("Are you kidding me?
"
); else { for(i=0; iif(xu[i] == 1) printf("1->2
"
); else if(xu[i] == 2) printf("1->3
"
); else if(xu[i] == 3) printf("3->2
"
); } } return 0; }

좋은 웹페이지 즐겨찾기