← 返回题目列表

AtCoder · practice2_d

D. 最大流量

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

分数: 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.#
^><