分数: 400 点
问题陈述
有一天,高桥参观了一家电影院,决定在每块地砖上画出箭头,每个箭头都指向最近的紧急出口。
给你一个网格 H 行和 W 列。让 (i, j) 表示位于 i从顶部开始的第行和 j左起第 列。
每个单元格由以下字符之一表示 S_{i,j}:
.:走廊单元#:壁细胞E:紧急出口
对于任何走廊单元 (i, j),定义 d(i, j),到最近紧急出口的距离,如下:
- 从 (i, j),重复移动到相邻的 非壁细胞 沿四个基本方向之一(上、下、左、右),直到到达紧急出口。 d(i, j) 是所需的最小移动次数。
保证 d(i, j) 可以为给定网格中的每个走廊单元定义;也就是说,每个走廊单元 (i, j) 至少有一个仅通过走廊单元即可到达的紧急出口。
在每个走廊单元格中准确写入一个箭头(向上、向下、向左或向右),以便满足以下条件:
- 对于每个走廊单元 (i, j),如果您从 (i, j) 并执行以下操作 d(i, j) 次,您到达紧急出口:
- 按照当前单元格中所写箭头的方向移动一个单元格。 (你不能移入墙内或网格外。)
约束
- 2 \le H \le 1000
- 2 \le W \le 1000
- 每个 S_{i,j} is
.,#,或E. - 每个走廊单元 (i, j) 至少有一个可到达的紧急出口。
- H 和 W 是整数。
输入
输入由标准输入按以下格式给出:
H W
S_{1,1}S_{1,2}\dots S_{1,W}
S_{2,1}S_{2,2}\dots S_{2,W}
\vdots
S_{H,1}S_{H,2}\dots S_{H,W}
输出
让 T_{i,j} 是单元格的状态 (i, j) 写完箭头后。 T_{i,j} 是以下之一:
^:带有向上箭头的走廊单元格v:带有向下箭头的走廊单元格<:带有向左箭头的走廊单元格>:带有向右箭头的走廊单元格#:壁细胞E:紧急出口
按以下格式输出网格:
T_{1,1}T_{1,2}\dots T_{1,W}
T_{2,1}T_{2,2}\dots T_{2,W}
\vdots
T_{H,1}T_{H,2}\dots T_{H,W}
如果存在多个解决方案,则将接受其中任何一个。
示例输入 1
3 4 ...E .#.. ....
示例输出 1
>>>E ^#>^ >>>^
让我们验证一下条件
示例输出中的 (2, 3) 。距离 (2, 3) 到最近的紧急出口是 2,并按照示例输出中写入的箭头进行两次操作即可到达紧急出口。
也可以验证每个其他走廊单元的条件。
示例输入 2
3 2 ## ## ##
示例输出 2
## ## ##
可能存在没有走廊牢房或紧急出口的情况。
示例输入 3
7 20 .................... ..#..#..####..#E##.. ..#..#..#..#..#..... ..E###..#..#..####.. .....#..#..E.....#.. .....#..####..####.. ....................
示例输出 3
>v<<<<<>>>>>>>>v<<<< >v#^<#^^####v^#E##vv >v#^<#v^#>v#vv#^<<<< >>E###vv#>v#vv####^< >>^<<#vv#>>E<<<<<#^< >>^<<#vv####^<####^< >>^<<<<<>>>>^<<<<<^<