📄 problem 1221.htm
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0047)http://acm.zju.edu.cn/show_problem.php?pid=1221 -->
<HTML><HEAD><TITLE>Problem 1221</TITLE>
<META http-equiv=Content-Type content="text/html; charset=gb2312">
<META content="MSHTML 6.00.2900.3199" name=GENERATOR></HEAD>
<BODY>
<CENTER><IMG src="Problem 1221.files/logo.gif" align=center></IMG></CENTER>
<HR>
<CENTER><FONT color=blue size=+2>Risk</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> 1660 <FONT color=green>Accepted
Submit:</FONT> 737 </CENTER>
<HR>
Risk is a board game in which several opposing players attempt to conquer the
world. The gameboard consists of a world map broken up into hypothetical
countries. During a player's turn, armies stationed in one country are only
allowed to attack only countries with which they share a common border. Upon
conquest of that country, the armies may move into the newly conquered country.
<P>During the course of play, a player often engages in a sequence of conquests
with the goal of transferring a large mass of armies from some starting country
to a destination country. Typically, one chooses the intervening countries so as
to minimize the total number of countries that need to be conquered. Given a
description of the gameboard with 20 countries each with between 1 and 19
connections to other countries, your task is to write a function that takes a
starting country and a destination country and computes the minimum number of
countries that must be conquered to reach the destination. You do not need to
output the sequence of countries, just the number of countries to be conquered
including the destination. For example, if starting and destination countries
are neighbors, then your program should return one. </P>
<P>The following connection diagram illustrates the sample input. </P>
<P align=center><IMG height=154 src="Problem 1221.files/showimg.gif"
width=458></P>
<P align=left><BR><B>Input</B></P>
<P align=left>Input to your program will consist of a series of country
configuration test sets. Each test set will consist of a board description on
lines 1 through 19. The representation avoids listing every national boundary
twice by only listing the fact that country I borders country J when I < J.
Thus, the Ith line, where I is less than 20, contains an integer X indicating
how many "higher-numbered" countries share borders with country I, then X
distinct integers J greater than I and not exceeding 20, each describing a
boundary between countries I and J. Line 20 of the test set contains a single
integer (1 <= N <= 100) indicating the number of country pairs that
follow. The next N lines each contain exactly two integers (1 <= A,B <=
20; A!=B) indicating the starting and ending countries for a possible conquest.
</P>
<P>There can be multiple test sets in the input; your program should continue
reading and processing until reaching the end of file. There will be at least
one path between any two given countries in every country configuration. </P>
<P><BR><B>Output</B></P>
<P>For each input set, your program should print the following message "Test Set
#T" where T is the number of the test set starting with 1. The next NT lines
each will contain the result for the corresponding test in the test set - that
is, the minimum number of countries to conquer. The test result line should
contain the start country code A the string " to " the destination country code
B ; the string ": " and a single integer indicating the minimum number of moves
required to traverse from country A to country B in the test set. Following all
result lines of each input set, your program should print a single blank line.
</P>
<P><BR><B>Sample Input</B></P>
<P>1 3 <BR>2 3 4 <BR>3 4 5 6 <BR>1 6 <BR>1 7 <BR>2 12 13 <BR>1 8 <BR>2 9 10
<BR>1 11 <BR>1 11 <BR>2 12 17 <BR>1 14 <BR>2 14 15 <BR>2 15 16 <BR>1 16 <BR>1 19
<BR>2 18 19 <BR>1 20 <BR>1 20 <BR>5 <BR>1 20 <BR>2 9 <BR>19 5 <BR>18 19 <BR>16
20 </P>
<P><BR><B>Sample Output</B></P>
<P>Test Set #1 <BR>1 to 20: 7 <BR>2 to 9: 5 <BR>19 to 5: 6 <BR>18 to 19: 2
<BR>16 to 20: 2 <BR></P>
<HR>
<FONT color=green size=+1>Problem Source: </FONT><I>South Central USA 1997</I>
<HR>
<CENTER><A href="http://acm.zju.edu.cn/submit.php?pid=1221">Submit</A>
<A href="http://acm.zju.edu.cn/list_problem.php?vol=3">Back</A>
<A
href="http://acm.zju.edu.cn/problem_status.php?pid=1221">Status</A> </CENTER>
<HR>
<CENTER>
<TABLE width="100%" border=0>
<TBODY>
<TR>
<TD align=right width="65%"><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></TD>
<TD align=right width="35%"><A href="http://www.zzhang.cn/"><FONT
color=#ffffff
size=-3>Book</FONT></A></TD></TR></TBODY></TABLE></CENTER></BODY></HTML>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -