神秘的别墅

神秘的别墅

测试数据来自 wjszez/1540

布莱克先生是土尔其总统的顾问,因此他也将前往参加北约峰会。他喜欢单独居住,远离商业中心的宾馆。于是他在奥瑞契佛加租了一间大的别墅。但有一件事搅扰了他:尽管大多数的房间都有电灯开关,但这些开关经常只能控制其它房间的灯而不是自己房间的。但是房产经纪人却认为这是一个特色,布莱克先生只能认为当电工们将开关连接到框架上时,他们是心不在焉的。
有些夜晚,布莱克先生回来的很晚,当他站在门厅中时,所有其它房间的灯都是关的。因为布莱克先生怕黑,所以他不敢进入黑暗的房间,也不敢关掉他所在房间的灯。布莱克先生想利用这些接错位置的开关帮助他前进。他希望能走到卧室并关掉卧室以外所有的灯。
编写程序,根据给定的房间说明,考虑当仅有门厅中亮的时候,你如何从门厅到卧室。不可以进入一个黑暗的房间,只能在房间中关自己房间的开关,最后时,除了卧室以外的灯其余的灯都必须关闭,每个房间都只有一盏灯。如果有几种办法可以通往卧室,你必须找出使用步数最少的方法。其中“从一个房间到另一个房间”,“开灯”和“关灯”每个过程算一步。

输入
输入文件第一行包含三个整数R,D和S。R表示别墅的房间数,1<=R<=10,D表示房间之间连接的门数,S表示别墅中灯的开关数。房间用数字1到R标识,1号房间表示门厅,R房间表示卧室。接下来的D行每行包含两个整数I和J,表示房间I和房间J之间有一扇门连接。接下来的S行每行包含两个整数K和L,表示房间K中有一个开关控制房间L中的电灯。

输出
输出一行解。如果对于布莱克先生有解,则输出“Mr.Black needs X Steps.”其中X表示来到他的卧室并将所有其它房间的灯关掉所需的最少步数。如果无解,输出“Poor Mr. Black! No sleep tonight!”

样例
VILLA.IN
3 3 4
1 2
1 3
3 2
1 2
1 3
2 1
3 2

VILLA.OUT
Mr. Black needs 6 steps.

信息

ID
1952
难度
(无)
分类
(无)
标签
递交数
0
已通过
0
通过率
?
上传者