CF1844E Great Grids

一个 $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})$ 组成，这两个单元格恰好共用一个角。你希望这两个单元格中的字母相同。 请判断是否存在一个满足所有约束条件的优秀网格。

每组测试包含多组测试用例。第一行包含测试用例数 $t$（$1 \le t \le 10^3$）。接下来是每组测试用例的描述。 每组测试用例的第一行包含三个整数 $n$、$m$ 和 $k$（$2 \le n, m \le 2 \times 10^3$，$1 \le k \le 4 \times 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 \times 10^3$。 保证所有测试用例中 $m$ 的总和不超过 $2 \times 10^3$。 保证所有测试用例中 $k$ 的总和不超过 $4 \times 10^3$。

对于每组测试用例，如果存在满足所有约束条件的优秀网格，输出 "YES"；否则输出 "NO"。 你可以用任意大小写输出答案。例如，"yEs"、"yes"、"Yes" 和 "YES" 都会被识别为肯定回答。

在第一个测试用例中，以下优秀网格满足所有约束条件： BABCCBCAACAB 在第二个测试用例中，两个约束条件意味着单元格 $(1,1)$ 和 $(2,2)$ 必须相同，单元格 $(1,2)$ 和 $(2,1)$ 也必须相同，这使得唯一的 $2 \times 2$ 子网格无法包含三种不同的字母。 由 ChatGPT 4.1 翻译