← 返回题目列表

Codeforces · 1844/E

E. 大网格

中文机器翻译题面 查看原题

如果满足以下三个条件,则 $$$n \times m$$$ 字符网格被称为优秀:

- 每个字符都是“A”、“B”或“C”。
- 每个 $$$2 \times 2$$$ 连续子网格包含所有三个不同的字母。
- 任何两个共享公共边的单元格都包含不同的字母。

让 $$$(x,y)$$$ 表示从顶部开始的第 $$$x$$$ 行和从左边开始的第 $$$y$$$ 列中的单元格。

您想要构建一个满足 $$$k$$$ 约束的出色网格。每个约束由两个单元格组成:$$$(x_{i,1},y_{i,1})$$$ 和 $$$(x_{i,2},y_{i,2})$$$,它们恰好共享一个角。您希望您的大网格在单元格 $$$(x_{i,1},y_{i,1})$$$ 和 $$$(x_{i,2},y_{i,2})$$$ 中具有相同的字母。

判断是否存在满足所有约束的大网格。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^3$$$)。测试用例的描述如下。

每个测试用例的第一行包含三个整数,$$$n$$$、$$$m$$$ 和 $$$k$$$ ($$$2 \le n,m \le 2 \cdot 10^3$$$, $$$1 \le k \le 4 \cdot 10^3$$$)。

接下来的 $$$k$$$ 行包含四个整数:$$$x_{i,1}$$$、$$$y_{i,1}$$$、$$$x_{i,2}$$$ 和 $$$y_{i,2}$$$ ($$$1 \le x_{i,1} < x_{i,2} \le n$$$, $$$1 \le y_{i,1},y_{i,2}\le m$$$)。保证 $$$(x_{i,2},y_{i,2}) = (x_{i,1}+1,y_{i,1}+1)$$$ 或 $$$(x_{i,2},y_{i,2}) = (x_{i,1}+1,y_{i,1}-1)$$$。

单元对是成对不同的,即对于所有 $$$1 \le i < j \le k$$$,$$$x_{i,1} = x_{j,1}$$$、$$$y_{i,1} = y_{j,1}$$$、$$$x_{i,2} = x_{j,2}$$$ 是不正确的,并且$$$y_{i,2} = y_{j,2}$$$。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^3$$$。

保证所有测试用例的 $$$m$$$ 总和不超过 $$$2 \cdot 10^3$$$。

保证所有测试用例的 $$$k$$$ 总和不超过 $$$4 \cdot 10^3$$$。

输出

对于每个测试用例,如果存在满足所有约束的大网格,则输出“YES”,否则输出“NO”。

您可以在任何情况下输出答案(大写或小写)。例如,字符串“yEs”、“yes”、“Yes”和“YES”将被识别为肯定响应。

示例

输入 #1

4
3 4 4
1 1 2 2
2 1 3 2
1 4 2 3
2 3 3 2
2 7 2
1 1 2 2
1 2 2 1
8 5 4
1 2 2 1
1 5 2 4
7 1 8 2
7 4 8 5
8 5 4
1 2 2 1
1 5 2 4
7 1 8 2
7 5 8 4

输出 #1

YES
NO
YES
NO

注意

在第一个测试用例中,以下大网格满足所有约束:BABCCBCAACAB

在第二个测试用例中,两个约束意味着单元格 $$$(1,1)$$$ 和 $$$(2,2)$$$ 具有相同的字母,并且单元格 $$$(1,2)$$$ 和 $$$(2,1)$$$ 具有相同的字母,这使得唯一的 $$$2 \times 2$$$ 子网格不可能包含所有三个不同的字母。