← 返回题目列表

Codeforces · 1898/C

C. 七彩网格

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

Elena 有一个由 $$$n$$$ 水平线和 $$$m$$$ 垂直线组成的网格。水平线从上到下按从 $$$1$$$ 到 $$$n$$$ 的整数进行编号。垂直线从左到右用从 $$$1$$$ 到 $$$m$$$ 的整数进行编号。对于每个 $$$x$$$ 和 $$$y$$$ ($$$1 \leq x \leq n$$$, $$$1 \leq y \leq m$$$),符号 $$$(x, y)$$$ 表示第 $$$x$$$ 水平线和第 $$$y$$$ 垂直线的交点。

两点 $$$(x_1,y_1)$$$ 和 $$$(x_2,y_2)$$$ 相邻当且仅当 $$$|x_1-x_2| + |y_1-y_2| = 1$$$。

由$$$n=4$$$水平线和$$$m=5$$$垂直线形成的网格。

当且仅当满足以下所有条件时,Elena 将长度为 $$$g$$$ 的点序列 $$$p_1, p_2, \ldots, p_g$$$ 称为游走:

- 此序列中的第一个点 $$$p_1$$$ 是 $$$(1, 1)$$$。
- 此序列中的最后一个点 $$$p_g$$$ 是 $$$(n, m)$$$。
- 对于每个 $$$1 \le i < g$$$,点 $$$p_i$$$ 和 $$$p_{i+1}$$$ 是相邻的。

请注意,步行可能多次包含同一点。特别是,它可能多次包含点 $$$(1, 1)$$$ 或 $$$(n, m)$$$ 。

Elena 网格中有 $$$n(m-1)+(n-1)m$$$ 段连接相邻点。 Elena 想要将这些段中的每一个着色为蓝色或红色,以便存在长度为 $$$k+1$$$ 的步行 $$$p_1, p_2, \ldots, p_{k+1}$$$,使得

- 在连接此行走中两个连续点的 $$$k$$$ 段中,没有两个连续段具有相同的颜色(换句话说,对于每个 $$$1 \le i < k$$$,点 $$$p_i$$$ 和 $$$p_{i+1}$$$ 之间的段的颜色不同于点 $$$p_{i+1}$$$ 和$$$p_{i+2}$$$)。

请查找任何此类着色或报告不存在此类着色。

输入

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

每个测试用例的唯一行包含三个整数 $$$n$$$、$$$m$$$ 和 $$$k$$$ ($$$3 \leq n,m \leq 16$$$, $$$1 \leq k \leq 10^9$$$) - 网格的尺寸和 Elena 正在寻找的步行中的段数。

输出

对于每个测试用例,如果无法将每个 $$$n(m-1)+(n-1)m$$$ 段着色为蓝色或红色,则输出“NO”,以便存在长度 $$$k+1$$$ 满足语句条件的游走。

否则,在第一行输出“YES”,然后提供所需的着色。

在着色描述的前 $$$n$$$ 行中,输出 $$$m-1$$$ 个空格分隔的字符。这些 $$$n$$$ 行中第 $$$i$$$ 行中的第 $$$j$$$ 个字符应表示点 $$$(i,j)$$$ 和 $$$(i,j+1)$$$ 之间的线段的颜色。这里,使用“B”表示蓝色,使用“R”表示红色。

在接下来的 $$$n-1$$$ 行着色描述中,输出 $$$m$$$ 个空格分隔的字符。这些 $$$n-1$$$ 行中的第 $$$i$$$ 行中的第 $$$j$$$ 个字符应表示点 $$$(i,j)$$$ 和 $$$(i+1,j)$$$ 之间的线段的颜色。同样,使用“B”表示蓝色,使用“R”表示红色。

您可以以任何大小写(大写或小写)输出答案中的每个字母。例如,字符串“yEs”、“yes”、“Yes”和“YES”将被识别为肯定响应,“R”和“r”都是红色的有效表示法。

示例

输入 #1

5
4 5 11
3 3 2
3 4 1000000000
3 3 12588
4 4 8

输出 #1

YES
R R B B
R R R R
B B B R
R R B B
R B B R B
R B B B B
B B R R R
NO
NO
YES
R B
B B
B R
B B R
R B B
YES
B B R
R B R
B R R
R R B
B R R B
B B B B
B R R R

注意

在第一个测试用例中,正确答案之一如下图所示。长度 $$$12$$$ 的颜色交替行走被突出显示。

在第二个和第三个测试用例中,可以表明没有着色满足语句中的条件。