a340. TOI 2020/04 潛力組：迷宮逃離

題目描述

迷宮有 N 間房間，每間房間的左右兩側各放一座雕像。要成功逃離，必須在每個房間恰好破壞一座雕像，保留另一座，並滿足所有線索。

每條線索指定兩座雕像，以及字母 S 或 D。S 表示兩座雕像最後狀態必須相同，即都被破壞或都被保留；D 表示它們的狀態必須不同。雕像用房間編號與 L、R 組成的字串表示，例如 1L 是第 1 間房間左側雕像。

請判斷是否至少存在一種符合全部線索的選擇方式。

輸入格式

第一行包含 N、T，表示房間數及線索數。

• 1 ≤ N ≤ 2000
• 1 ≤ T ≤ N^2

接下來 T 行各有兩個雕像字串及一個大寫字母 S 或 D。房間編號為 1 至 N，雕像位置為 L 或 R。例如「1L 2R S」要求第 1 間左側與第 2 間右側雕像狀態相同。

分組：10 分滿足 N≤10；30 分滿足 N≤300；60 分滿足 N≤2000。

輸出格式

若存在符合要求的破壞方式，輸出 Easy Peasy；否則輸出 Impossible。

範例 1 可破壞 1R、2R、3L，也可破壞 1L、2L、3R。範例 2 則無法同時滿足所有線索。

範例 1

輸入：

3 2
1L 2L S
2L 3R S

輸出：

Easy Peasy

範例 2

輸入：

3 3
1L 2L S
2L 3R S
3L 1R D

輸出：

Impossible

來源

TOI 2020/04 練習賽潛力組〈迷宮逃離〉。依官方原題 PDF 自行整理，所有範例均取自原件。

原題連結：https://tpmso.k12ea.gov.tw/toi/wp-content/uploads/question/202004/A3-Escape.pdf