|
|
вернуться в форумThe problem is simple.But you must care that if N(different compartments)=0 you should output 0 instead of -1 Послано Y.Y.M. 22 июн 2004 20:34 Re: The problem is simple.But you must care that if N(different compartments)=0 you should output 0 instead of -1 Послано Magvay 5 сен 2004 18:25 thanks a lot. I really didn't know what to do with test 13 It's not number of compartments=0. If you don't ignore the first line of input there'll be no this problem. Re: The problem is simple.But you must care that if N(different compartments)=0 you should output 0 instead of -1 Cockroaches!蟑螂
Time Limit: 1 second
Memory Limit: 1000K
It's well-known that the most tenacious of life species on the Earth are cockroaches. They live everywhere if only there in food. And as far as they are unpretentious in food you can find them absolutely everywhere.
众所周知地球上最顽强的生命种类是蟑螂，他们生活在有食物的任何地方。只要有食物，你就可以发现他们的影踪。
A little Lyosha studies at school on a Space station. During one of the school competitions his class has reached the final. A task of the final contest is to exterminate all the cockroaches in the cargo module within minimal time.
Lyosha 在太空站的学校学习。在学校的一项竞赛里，他们班已经到达接近尾声，其中一项任务是在最小的时间里消灭货物仓里的蟑螂。
Within the long history of the competitions a unified tactics was worked out. The tactics is as follows: a poison gas is let in one of the module compartments and after that the baffle that separates the compartment from one of the adjacent ones is opened. Cockroaches can't stand the smell of the gas and run to the other compartment. When there's no cockroaches in the treated compartment the baffle is closed. Afterwards analogously the next compartment is treated, and so on. The goal is to move all the cockroaches to the floodgate of the cargo module. Then the outward door is opened and all the cockroaches are engulfed by an open Space.
他们在长时间的竞赛里，已经形成了统一的战术。 战术是这样的：把毒气放在一个厢房里，另外，打开闸门（隔开相邻厢房的门）。蟑螂不能忍受毒气的味道，会纷纷逃向隔壁的已打开的厢房，如此下去。目标是把所有的蟑螂赶向floodgate货物仓（的闸门）。
Lyosha is responsible for programming the control board of the baffles in his team. The baffles are opened slowly, so it's very important to make do with minimal number of baffle openings in order to win in the contest. Your task is to help Lyosha to compute this number.
Lyosha负责闸门的规划控制，闸门开得慢，所以这项工作对于竞赛的胜负是很重要的，要设法使到开最少的门。你的任务是帮助Lyosha 计算这个数。
Input
The first line contains a name of the floodgate compartment. Each of the next lines contains description of one of the baffles - the names of two compartments separated with a dash (-). The last line contains the only symbol "#". There are cockroaches in all the compartments of the module at first. It's possible to get to the floodgate from every compartment of the module passing several baffles. The total number of compartments doesn't exceed 30. The name of a compartment consists of no more than 20 Latin letters and digits. The large and the small letters should be distinguished.
首行为floodgate厢房名。以下每一行为两个厢房间的闸门名，两个厢房间用(-)隔开。最后一行只有“#”结束。开始时每个厢房都有蟑螂。每个厢房的蟑螂经过几个闸门后都能到达floodgate。厢房的数量不超过30个。厢房名不超过20个字母数字，区分大小写。
Output
Your program is to output the only number - the minimal amount of baffles that should be opened (and then closed) in order to move all the cockroaches to the floodgate.
输出最小的数字，即为了能把蟑螂赶到指定的floodgate,要开的门数 （当然开完后又关上）
Sample Input
Gateway
Machinery-Gateway
Machinery-Control
Control-Central
Control-Engine
Central-Engine
Storage-Gateway
Storage-Waste
Central-Waste
#
Sample Output
6
Re: The problem is simple.But you must care that if N(different compartments)=0 you should output 0 instead of -1 thx anyway for translating it to Chinese Re: The problem is simple.But you must care that if N(different compartments)=0 you should output 0 instead of -1 Thank, I have Got WA13) now AC Re: The problem is simple.But you must care that if N(different compartments)=0 you should output 0 instead of -1 I just want to know why the answer is Number_comparments - 1 Re: The problem is simple.But you must care that if N(different compartments)=0 you should output 0 instead of -1 Because you can make a tree from comparments and then open the baffles from the leaves to the root of tree using only n-1 baffle. |
|
|
