← 返回题目列表

AtCoder · arc219_e

E. 平均分配

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

分数: 600 点

问题陈述

有一个形状像 2H \times 2W 网格。牢房位于 i从顶部开始的第行和 j从左边算起的第列表示为单元格 (i,j)。细胞 (i,j) 上面有一个草莓,如果 S_{i,j}= o,如果 S_{i,j}= x。可以保证准确地说 2HW 细胞有草莓。

将此酥饼的每个单元格划分为区域 A 和 B,以满足以下所有条件:

  • 每个单元格都属于区域 A 和 B 之一。
  • 区域 A 和 B 均已连接。也就是说,对于同一区域中的任意两个小区,可以通过重复移动到同一区域中的相邻小区(共享边缘)来在它们之间移动。
  • 区域 A 和 B 均包含 每个 2HW 细胞。
  • 区域 A 和 B 均包含 每个 HW 草莓各一个。

可以证明这样的分区总是存在的。

你被给予 T 测试用例;解决它们中的每一个。

约束

  • 1\le T
  • 1\le H\le W
  • H\times W\le 10^6
  • S_{i,j} is o or x.
  • 正好有 2HW 对 (i,j) 与 S_{i,j}= o.
  • 总和 H\times W 所有测试用例最多 10^6.
  • T, H, W 是整数。

输入

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

T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T

每个测试用例均按以下格式给出:

H W
S_{1,1} S_{1,2} \ldots S_{1,2W}
S_{2,1} S_{2,2} \ldots S_{2,2W}
\vdots
S_{2H,1} S_{2H,2} \ldots S_{2H,2W}

输出

按顺序输出测试用例的解决方案,以换行符分隔。

对于每个测试用例,按以下格式输出您的解决方案:

X_{1,1} X_{1,2} \ldots X_{1,2W}
X_{2,1} X_{2,2} \ldots X_{2,2W}
\vdots
X_{2H,1} X_{2H,2} \ldots X_{2H,2W}

在这里, X_{i,j} is A 如果细胞 (i,j) 属于区域 A,并且 B 如果属于区域B。

如果存在多个有效分区,则其中任何一个都将被接受。


示例输入 1

3
1 1
ox
xo
1 2
oxxx
ooxo
2 3
oooxxx
oooxxx
xoxxxx
xooooo

示例输出 1

AA
BB
AAAB
ABBB
AAABBB
AAAAAB
ABABAB
ABBBBB

考虑第一个测试用例。

在示例输出中,区域 A 和 B 都是相连的,并且各包含两个单元格。此外,A 区包含单元格中的草莓 (1,1),区域 B 包含单元格中的草莓 (2,2).

此外,例如,接受以下输出:

AB
AB