分数: 100 点
问题陈述
给你一个网格 N 行和 M 列。广场位于 i第行和 j第列将表示为 (i,j)。
一些方块包含一个物体。所有剩余的方块都是空的。
网格的状态由字符串表示 S_1,S_2,\cdots,S_N。广场 (i,j) 包含一个对象,如果 S_{i,j}= # 并且为空,如果 S_{i,j}= ..
考虑放置 1 \times 2 网格上的图块。瓷砖可以垂直或水平放置以覆盖两个相邻的空方块。 瓷砖不得伸出网格,并且两个不同的瓷砖不得相交。瓷砖不能占据带有物体的方块。
计算可以放置的图块的最大数量以及达到最大值的任何配置。
约束
- 1 \leq N \leq 100
- 1 \leq M \leq 100
- S_i 是一个长度为 M 包括
#和..
输入
输入由标准输入按以下格式给出:
N M S_1 S_2 \vdots S_N
输出
在第一行,打印可以放置的最大块数。
上下 N 行,打印达到最大值的配置。 准确地说,输出字符串 t_1,t_2,\cdots,t_N 通过以下方式构建。
- t_i 被初始化为 S_i.
- 对于每个 (i,j),如果有一个图块占据 (i,j) 和 (i+1,j),更改 t_{i,j}:=
v, t_{i+1,j}:=^. - 对于每个 (i,j),如果有一个图块占据 (i,j) 和 (i,j+1),更改 t_{i,j}:=
>, t_{i,j+1}:=<.
请参阅示例以了解更多信息。
您可以打印任何使图块数量最大化的配置。
示例输入 1
3 3 #.. ..# ...
示例输出 1
3 #>< vv# ^^.
以下输出也被视为正确答案。
3 #>< v.# ^><