← 返回题目列表

AtCoder · agc059_e

E. 网格 3 着色

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

分数: 1400 点

问题陈述

你有一个 N \times N 网格板。 您想要为所有单元格着色 3 颜色,使两个相邻(共享边缘)的单元格不具有相同的颜色。

您已经绘制了板的边框。确定是否可以正确为板的其余部分着色。

更准确地说,你得到一个字符串 S 长度 4N-4 由字符组成 1, 2,和 3。该字符串表示边框上单元格的颜色,从单元格开始 (1, 1),按顺时针顺序。 严格来说, i第一个字符 S 表示单元格的颜色:

  • (1, i) 为 1 \le i \le N-1
  • (i - (N-1), N) 为 N \le i \le 2N-2
  • (N, 3N - 1 - i) 为 2N-1 \le i \le 3N-3
  • (4N-2 - i, 1) 为 3N-2 \le i \le 4N-4.

在这里, (r,c) 表示单元格中 r第行和 c第列。

保证边界上没有两个相邻单元格具有相同的颜色。

解决 T 每个输入文件的测试用例。 一个输入文件中的

约束

  • 1 \le T \le 5 \cdot 10^4
  • 3 \le N \le 2 \cdot 10^5
  • S 是一个长度为的字符串 4N-4 由字符组成 1, 2,和 3.
  • S_i \neq S_{i+1} 为 1 \le i \le 4N-5,和 S_{4N-4} \neq S_1.
  • 总和 N 不超过 2\cdot 10^5.
  • 输入中的所有数字均为整数。

输入

输入由标准输入按以下格式给出:

T
case_1
case_2
\vdots
case_T

每个案例的格式如下:

N
S

输出

对于每个测试用例,输出 YES 如果有办法给棋盘的其余部分着色 3 颜色正确,并且 NO 否则。您可以以任何大小写(大写或小写)输出每个字母。


示例输入 1

4
3
12312312
4
121212121212
7
321312312312121212121321
7
321312312312121312121321

示例输出 1

NO
YES
NO
YES

可以看出,在第一个和第三个测试用例中无法正确为电路板的其余部分着色。第二个和第四个测试用例的正确颜色如下所示。