红色涂格(Red Painting)

题目描述

本题对应 AtCoder Typical 90 第 012 题：Red Painting。

有一个 $H$ 行 $W$ 列的网格，初始时所有格子均为白色。接下来有 $Q$ 次操作，操作分为以下两种类型：

• 1 r c：将第 $r$ 行第 $c$ 列的格子涂成红色（若已经是红色则保持红色不变）；
• 2 ra ca rb cb：询问能否仅通过四连通（上下左右相邻）的红色格子，从格子 $(r_a, c_a)$ 走到格子 $(r_b, c_b)$。注意：若起点或终点本身不是红色，则视为不能到达。

输入格式

第一行包含两个正整数 $H, W$。

第二行包含一个正整数 $Q$。

接下来 $Q$ 行，每行描述一次操作，格式如题面所示。

输出格式

对于每个类型 2 的询问，若能到达则输出一行 Yes，否则输出一行 No。

样例输入 #1

3 3
10
1 2 2
1 1 1
2 1 1 2 2
1 3 2
2 1 1 2 2
2 2 2 3 2
1 2 3
1 2 1
2 1 1 2 2
2 1 1 3 3

样例输出 #1

No
No
Yes
Yes
No

数据范围

对于 $100\%$ 的数据，$1 \le H, W \le 2000$，$1 \le Q \le 10^5$。

知识点与难度

本题涉及的知识点从属于 CSP-S，难度（CF Rating）：1400。

测试点分布

出处：原题链接