7 - 2 열 객차 스케줄 링 (25 point (s)) (창고 의 고전 제목)
3174 단어 데이터 구조
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;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.