#P3082. 'Roid Rage

'Roid Rage

题目描述 你是 Jellern 公司最新家庭安全软件 Securitron 9042 的首席程序员。该软件旨在 “保护” 一个房间,具体方式是确定需要锁定的最少门数,以防止从一个或多个房间进入指定房间。每个门连接两个房间,且有一个控制面板,该面板仅可从一侧操作(即仅在某个房间内可通过该面板解锁此门)。例如,若某房屋布局如下:

(此处为示意图描述,原文中可能有图示,此处省略)

房间编号为 060-6$,控制面板标记为 “CP”(位于可操作的房间内,即该房间可通过面板解锁对应门)。此时,若要确保房间 22 不被房间 11 进入,需锁定 22 扇门:房间2 211 之间的门,以及房间 33 与 $1% 之间的门。注意,无法确保房间 22 不被房间 33 进入,因为房间 33 内的控制面板可解锁其与房间 22 之间的门。 输入 输入以一个整数xx开始,表示数据集数量。每个数据集包含:

起始行:包含两个整数mmn1m200n19n(1≤m≤20,0≤n≤19),其中m为房间总数,nn为需要保护的房间(恐慌房间)。 房间列表:共mm行,依次描述每个房间(从房间 00 到房间 m1m-1)。每行内容包括: 第一个值为II(表示该房间有入侵者)或NINI(无入侵者)。 第二个值为整数cc,表示该房间内可操作的门数(即该房间内有控制面板的门,可通向其他房间)。 后续cc个整数,为这些门所连接的房间号(按升序排列)。 输出 对每个数据集,输出确保恐慌房间不被任何入侵者进入所需的最少锁门数。若无法做到这一点,输出 “PANIC ROOM BREACH”。假设所有门初始为未锁定状态,且恐慌房间内无入侵者。