Algorithm 版 (精华区)

发信人: xiaoying (xiaoying), 信区: Algorithm
标  题: 1103P-Hike on a Graph-ZJU
发信站: 哈工大紫丁香 (2002年10月09日17:18:35 星期三), 站内信件

Hike on a Graph
----------------------------------------------------------------------------
----
Time limit: 30 Seconds   Memory limit: 32768K
Total Submit: 56   Accepted Submit: 18
----------------------------------------------------------------------------
----
"Hike on a Graph" is a game that is played on a board on which an undirected
 graph is drawn. The graph is complete and has all loops, i.e. for any two l
ocations there is exactly one arrow between them. The arrows are coloured. T
here are three players, and each of them has a piece. At the beginning of th
e game, the three pieces are in fixed locations on the graph. In turn, the p
layers may do a move. A move consists of moving one's own piece along an arr
ow to a new location on the board. The following constraint is imposed on th
is: the piece may only be moved along arrows of the same colour as the arrow
 between the two opponents' pieces.
In the sixties ("make love not war") a one-person variant of the game emerge
d. In this variant one person moves all the three pieces, not necessarily on
e after the other, but of course only one at a time. Goal of this game is to
 get all pieces onto the same location, using as few moves as possible. Find
 out the smallest number of moves that is necessary to get all three pieces 
onto the same location, for a given board layout and starting positions.
Input Specification
The input file contains several test cases. Each test case starts with the n
umber n. Input is terminated by n=0. Otherwise, 1<=n<=50. Then follow three 
integers p1, p2, p3 with 1<=pi<=n denoting the starting locations of the gam
e pieces. The colours of the arrows are given next as a m×m matrix of white
space-separated lower-case letters. The element mij denotes the colour of th
e arrow between the locations i and j. Since the graph is undirected, you ca
n assume the matrix to be symmetrical.
Output Specification
For each test case output on a single line the minimum number of moves requi
red to get all three pieces onto the same location, or the word "impossible"
 if that is not possible for the given board and starting locations.
Sample Input
3 1 2 3
r b r
b b b
r b r
2 1 2 2
y g
g y
0
 Sample Output
2
impossible

--

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 202.118.226.228]