|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|8 초 (추가 시간 없음)||512 MB||0||0||0||0.000%|
The National Association of Museum Curators came to you with an interesting problem. The President of the country, in order to improve his public image, has decided to visit the various Art Museums in the country, to convey the impression that he is a refined man. Being a very busy person, however, and knowing nothing about art, he imposed two restrictions for the visits:
The curators are willing to follow the President’s demands, but they do not want to redistribute the masterpieces in the exposition only to obtain a straight path. Their only concession is to exchange temporarily the place of two masterpieces, if this helps to obtain a shorter path.
You should write a program that receives as input the layout of an exposition and finds the shortest path, according to the above constraints. To make your task easier, the curators have already defined a standard layout. Figure 7 shows one such layout.
Figure 7: Layout of the Museum
The President’s walk begins always at the left wall (X = 1, any Y) and ends at the right wall (X = Xmax, any Y). The walk can be done horizontally or vertically; diagonal movements are not allowed. The works of a given artist are all labeled with the same capital letter (A, B, C, etc). From Figure 1, several cases can be illustrated:
The input file may contain several instances of the problem. Each instance has the following format (all numbers are positive integers):
A line containing two zeros terminates the input file. Numbers are separated by spaces.
For each instance of the problem, your program should produce output as follows.
If a path exists, your program should first print one line with the message “
Exchange (x,y) and (u,v)” if an exchange will occur, or “
No exchange” otherwise. Following that, the shortest path should be printed, one coordinate per line. In case more than one path is the shortest, any one of them may be printed, except that a path without an exchange should be preferred to those with exchanges.
If a path does not exist, your program should print only one line with the message “
The output of each instance is terminated with a blank line.
11 10 A BBBBBBFFFFF AAAAABDCCFF AFFFABAACFC BFEFABBBBBD FFDEABAAABA EEDEEEEEABB DDDEEEEEAAB DCCFFFCCABA DCCFFFCCAAA CCCCCCCCCCC 11 10 C BBBBBBFFFFF AAAAABDCCFF AFFFABAACFC BFEFABBBBBD FFDEABAAABA EEDEEEEEABB DDDEEEEEAAB DCCFFFCCABA DCCFFFCCAAA CCCCCCCCCCC 0 0
Exchange (6,6) and (1,8) 1 9 2 9 3 9 4 9 5 9 5 8 5 7 5 6 6 6 7 6 8 6 9 6 9 5 9 4 9 3 9 2 10 2 11 2 No exchange 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 1 11 1