AT_agc059_e [AGC059E] Grid 3-coloring
题目描述
有一个 $N \times N$ 的方格棋盘。你需要用三种颜色给所有格子染色，要求任意相邻（共享边）的两个格子颜色不同。
棋盘最外层的格子已经被染色。请判断是否可以按照要求给剩下的格子染色。
更准确地说，给定一个由字符 `1`、`2`、`3` 组成的长度为 $4N-4$ 的字符串 $S$，该字符串表示从 $(1, 1)$ 开始，按顺时针顺序记录的最外层格子的颜色。具体地，第 $i$ 个字符表示如下格子的颜色：
- 当 $1 \leq i \leq N-1$ 时，对应 $(1, i)$；
- 当 $N \leq i \leq 2N-2$ 时，对应 $(i - (N-1), N)$；
- 当 $2N-1 \leq i \leq 3N-3$ 时，对应 $(N, 3N-1-i)$；
- 当 $3N-2 \leq i \leq 4N-4$ 时，对应 $(4N-2-i, 1)$。
其中，$(r, c)$ 表示第 $r$ 行第 $c$ 列的格子。
保证最外层格子中，任意相邻的两个格子颜色不同。
对于每个输入文件，请判断是否存在一种方案，可以用三种颜色给剩下的格子染色，使得任意相邻格子颜色不同。
输入格式
输入从标准输入读入，格式如下：
> $T$
> $case_1$
> $case_2$
> $\vdots$
> $case_T$
每个测试用例格式如下：
> $N$ $S$
输出格式
对于每个测试用例，如果存在一种方案可以按照要求用三种颜色染色，则输出 `YES`，否则输出 `NO`。输出时不区分大小写。
说明/提示
### 限制
- $1 \leq T \leq 5 \cdot 10^4$
- $3 \leq N \leq 2 \cdot 10^5$
- $S$ 是由字符 `1`、`2`、`3` 组成的长度为 $4N-4$ 的字符串。
- 对于 $1 \leq i \leq 4N-5$，有 $S_i \neq S_{i+1}$，且 $S_{4N-4} \neq S_1$。
- 每个输入文件中所有 $N$ 的总和不超过 $2 \cdot 10^5$。
- 输入中的所有数字均为整数。
### 样例解释 1
对于第一个和第三个测试用例，可以证明无法按照要求染色。对于第二个和第四个测试用例，下面给出了可以按照要求染色的方案。
由 ChatGPT 4.1 翻译