#P3082. 'Roid Rage
'Roid Rage
题目描述 你是 Jellern 公司最新家庭安全软件 Securitron 9042 的首席程序员。该软件旨在 “保护” 一个房间,具体方式是确定需要锁定的最少门数,以防止从一个或多个房间进入指定房间。每个门连接两个房间,且有一个控制面板,该面板仅可从一侧操作(即仅在某个房间内可通过该面板解锁此门)。例如,若某房屋布局如下:
(此处为示意图描述,原文中可能有图示,此处省略)
房间编号为 $,控制面板标记为 “CP”(位于可操作的房间内,即该房间可通过面板解锁对应门)。此时,若要确保房间 不被房间 进入,需锁定 扇门:房间 与 之间的门,以及房间 与 $1% 之间的门。注意,无法确保房间 不被房间 进入,因为房间 内的控制面板可解锁其与房间 之间的门。 输入 输入以一个整数开始,表示数据集数量。每个数据集包含:
起始行:包含两个整数和,其中m为房间总数,为需要保护的房间(恐慌房间)。 房间列表:共行,依次描述每个房间(从房间 到房间 )。每行内容包括: 第一个值为(表示该房间有入侵者)或(无入侵者)。 第二个值为整数,表示该房间内可操作的门数(即该房间内有控制面板的门,可通向其他房间)。 后续个整数,为这些门所连接的房间号(按升序排列)。 输出 对每个数据集,输出确保恐慌房间不被任何入侵者进入所需的最少锁门数。若无法做到这一点,输出 “PANIC ROOM BREACH”。假设所有门初始为未锁定状态,且恐慌房间内无入侵者。