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
*
注意
第一种情况,确实有两种解决方案:
和
所以答案是“不是唯一的”。