← 返回题目列表

Codeforces · 515/D

D. Drazil 和瓷砖

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

Drazil 创建了一个关于将 1 × 2 块放入 n × m 网格的问题:

“有一个网格,其中一些单元格是空的,一些单元格被占用。您应该使用 1 × 2 块来覆盖所有空单元格,并且任何两个块都不应相互覆盖。并且您应该打印一个有关如何执行此操作的解决方案。”

但 Drazil 不喜欢为此任务编写特殊的检查程序。他的朋友 Varda 建议他:“不如要求参赛者只打印存在且唯一的解决方案?否则参赛者可能会打印‘不唯一’”。

Drazil发现这个任务的约束可能比原来的任务大得多!

你能解决这个新问题吗?

请注意,当不存在解决方案或原始任务存在多个不同的解决方案时,您应该打印“Not unique”。

输入

第一行包含两个整数 n 和 m (1 ≤ n, m ≤ 2000)。

以下 n 行描述网格行。特点 '。'表示空单元格,字符“*”表示已占用的单元格。

输出

如果没有解或解不唯一,则应打印字符串“Not unique”。

否则,您应该打印如何用 1 × 2 块覆盖所有空单元格。使用字符“<>”表示水平图块,使用字符“^v”表示垂直图块。有关输出格式示例,请参阅示例测试。

示例

输入 #1

3 3
...
.*.
...

输出 #1

Not unique

输入 #2

4 4
..**
*...
*.**
....

输出 #2

<>**
*^<>
*v**
<><>

输入 #3

2 4
*..*
....

输出 #3

*<>*
<><>

输入#4

1 1
.

输出#4

Not unique

输入 #5

1 1
*

输出 #5

*

注意

第一种情况,确实有两种解决方案:

和

所以答案是“不是唯一的”。