📄 problem 1103.htm
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0047)http://acm.zju.edu.cn/show_problem.php?pid=1103 -->
<HTML><HEAD><TITLE>Problem 1103</TITLE>
<META http-equiv=Content-Type content="text/html; charset=gb2312">
<META content="MSHTML 6.00.2900.2769" name=GENERATOR></HEAD>
<BODY>
<CENTER><IMG src="Problem 1103.files/logo.gif" align=center></IMG></CENTER>
<HR>
<CENTER><FONT color=blue size=+2>Hike on a Graph</FONT></CENTER>
<HR>
<CENTER><FONT color=green>Time limit:</FONT> 1 Seconds <FONT
color=green>Memory limit: </FONT>32768K </FONT><BR><FONT
color=green>Total Submit:</FONT> 482 <FONT color=green>Accepted
Submit:</FONT> 235 </CENTER>
<HR>
<P>"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
locations there is exactly one arrow between them. The arrows are coloured.
There are three players, and each of them has a piece. At the beginning of the
game, the three pieces are in fixed locations on the graph. In turn, the players
may do a move. A move consists of moving one's own piece along an arrow to a new
location on the board. The following constraint is imposed on this: the piece
may only be moved along arrows of the same colour as the arrow between the two
opponents' pieces.
<P>In the sixties ("make love not war") a one-person variant of the game
emerged. In this variant one person moves all the three pieces, not necessarily
one 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.
<P><B>Input Specification</B>
<P>The input file contains several test cases. Each test case starts with the
number <I>n</I>. Input is terminated by <I>n=0</I>. Otherwise,
<I>1<=n<=50</I>. Then follow three integers <I>p<SUB>1</SUB>,
p<SUB>2</SUB>, p<SUB>3</SUB></I> with <I>1<=p<SUB>i</SUB><=n</I> denoting
the starting locations of the game pieces. The colours of the arrows are given
next as a <I>m×m</I> matrix of whitespace-separated lower-case letters. The
element <I>m<SUB>ij</SUB></I> denotes the colour of the arrow between the
locations <I>i</I> and <I>j</I>. Since the graph is undirected, you can assume
the matrix to be symmetrical.
<P><B>Output Specification</B>
<P>For each test case output on a single line the minimum number of moves
required 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.
<P>
<TABLE width="100%">
<TBODY>
<TR>
<TD vAlign=top>
<P><B>Sample Input</B>
<P><PRE>3 1 2 3
r b r
b b b
r b r
2 1 2 2
y g
g y
0
</PRE></TD>
<TD vAlign=top>
<P><B>Sample Output</B>
<P><PRE>2
impossible
</PRE></TD>
<TD vAlign=top><IMG src="Problem 1103.files/showimg.gif">
</TD></TR></TBODY></TABLE>
<HR>
<FONT color=green size=+1>Problem Source: </FONT><I>University of Ulm Local
Contest 2000</I>
<HR>
<CENTER><A href="http://acm.zju.edu.cn/submit.php?pid=1103">Submit</A>
<A href="http://acm.zju.edu.cn/list_problem.php?vol=2">Back</A>
<A
href="http://acm.zju.edu.cn/problem_status.php?pid=1103">Status</A> </CENTER>
<HR>
<CENTER><A href="http://acm.zju.edu.cn/"><FONT color=red>Zhejiang University
Online Judge</FONT></A> <A href="http://acm.zju.edu.cn/"><FONT
color=red>V1.0</FONT></A><BR></CENTER></BODY></HTML>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -