#P17830. [Ontak2022]MUL
[Ontak2022]MUL
题目描述
一个 的矩形棋盘被分成单位格,每格属于 名玩家中的一人。一次操作只改变一个格子的所有者,允许某名玩家没有任何格子。
棋盘合法当且仅当同时满足:
- 每名玩家的全部格子通过四连通相连,即相邻两格必须共边;空集合也允许。
- 任意玩家不能把其他玩家完全包围。具体地,对于任意属于玩家 的格子和任意 ,都必须存在一条通向棋盘边界的路径,路径不经过玩家 的任何格子,相邻两格允许共边或共角,即按八连通行走。
已知初始棋盘合法。依次检查 个提议:如果按提议改变所有者后棋盘合法,则接受并执行;否则拒绝,棋盘保持原状。
输入格式
第一行四个整数 。
接下来 行,每行 个 内的整数,表示初始所有者。
接下来 行,每行三个整数 ,表示把第 行、第 列改归玩家 。
输出格式
对每个提议输出一行:接受则输出 YES,拒绝则输出 NO。
数据范围
;;;,,。初始状态保证合法;把格子改为原所有者也是允许出现的提议。
子任务
| 子任务 | 附加限制 | 分值 |
|---|---|---|
| 1 | N=1 | 7 |
| 2 | N=2 | 11 |
| 3 | N=3 | 13 |
| 4 | K≤4 且 Q≤10 | 17 |
| 5 | Q≤10 | 19 |
| 6 | 无额外限制 | 33 |
样例 1
输入:
3 4 4 6
1 1 1 1
1 2 2 1
1 1 1 3
3 4 1
3 4 2
3 4 3
3 4 4
2 2 1
1 1 3
输出:
NO
NO
YES
YES
YES
YES