← 返回题目列表

AtCoder · abc405_d

G. 逃生路线

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

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