#CW78. 迷宫游戏(maze)
迷宫游戏(maze)
题目描述
迷宫有 个房间,房间编号为 。 表示房间 有出口, 表示没有出口。恰有 对房间之间存在无向通道;对于第 对房间 ,有 条互不相同的通道连接这两个房间。不保证任意两个房间之间都能通过通道相互到达。
一次游戏给出起点 和整数 。Alice 最初位于房间 。每轮她在当前房间 选择恰好 条与 相连且互不相同的通道;即使连接同一对房间,也可以选择其中的多条不同通道。如果与 相连的通道总数少于 ,Alice 立即输掉游戏。随后 Bob 从 Alice 所选的 条通道中选择一条,Alice 沿该通道移动到另一端的房间。
Alice 可以重复上述过程任意多次,包括 0 次;一旦到达有出口的房间,她立即获胜。若起点 本身有出口,则无需移动即可获胜。Alice 尽力获胜,Bob 尽力阻止她。若存在一种策略,使得无论 Bob 如何选择,Alice 最终都能到达有出口的房间,则她能够获胜;否则她无法获胜。请对每局游戏判断 Alice 是否能够获胜。
输入格式
从 maze.in 文件中读入。
第一行包含 ,分别表示房间数、存在通道的房间对数和游戏局数,满足 、、。第二行包含 个 ,表示各房间是否有出口。接下来 行包含 ,表示房间 之间有 条通道,满足 、;任意两行给出的房间对不同。最后 行包含 ,分别表示第 局游戏的起点和每轮必须选择的通道数,满足 、。
输出格式
向 maze.out 文件中输出。
输出 行;第 行若 Alice 能在第 个游戏中获胜则输出 YES,否则输出 NO。
样例 1 输入
5 5 5
0 0 1 0 0
1 2 1
1 3 1
1 4 2
2 3 2
3 4 1
2 1
1 2
3 3
4 4
5 1
样例 1 输出
YES
YES
YES
NO
NO
样例 2 输入
4 3 4
1 0 0 0
1 2 2
2 3 3
3 4 1
1 3
2 2
3 3
4 1
样例 2 输出
YES
YES
NO
YES
样例 3 输入
4 3 3
0 1 1 0
1 2 1
1 3 3
1 4 2
4 2
1 3
4 3
样例 3 输出
YES
YES
NO
样例 4 输入
2 0 2
1 0
1 1
2 1
样例 4 输出
YES
NO
数据范围
所有输入数据均为整数。
本题采用子任务捆绑计分:通过一个子任务的全部测试点,才能获得该子任务的分数。
| 子任务 | 分值 | 测试点 | 附加条件 |
|---|---|---|---|
| 1 | 6 | 图为链:,第 条通道连接 与 ,且仅房间 1 为出口 | |
| 2 | 8 | 图为星:,每条通道连接房间 1 与某个房间 | |
| 3 | 7 | ||
| 4 | 14 | ||
| 5 | 15 | ||
| 6 | 16 | ,且所有 | |
| 7 | 34 | 无额外限制 |