AT_abc405_d.[ABC405D] Escape Route

普及-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

高桥去到了电影院。在电影院的地面上，每块瓷砖上都画有指向最近的安全出口的箭头。

给你一个 $H$ 行 $W$ 列的网格 $S$ ，其中 . 表示空白地面，# 表示不可穿过的墙，E 表示安全出口。

在一个空白格子，你可以用一步移动到相邻的非墙格子。两个格子相邻当且仅当它们有公共的边。

令从一个空白格子 $(i,j)$ 移动到任意一个安全出口需要的最小步数为 $d(i,j)$ 。
你需要在所有空白的格子上画上箭头（指向上下左右中的一个），使得从每一个空白格子 $(i,j)$ 开始，每次向当前所在格子的箭头方向走一步，恰好 $d(i,j)$ 步后将到达安全出口。

数据保证每一个空白格子都可以到达至少一个安全出口。

输入格式

第一行两个整数 $H,W(2\le H,W\le 1000)$ 。
接下来 $H$ 行，每行一个长度为 $W$ 的字符串，构成网格 $S$ 。

数据保证每一个空白格子都可以到达至少一个安全出口。

输出格式

输出在所有空白格子填上箭头后的 $S$ 。你要用 ^ 表示向上的箭头，v 表示向下的箭头，< 表示向左的箭头，> 表示向右的箭头。

输入输出样例

输入#1
```
3 4
...E
.#..
....
```
输出#1
```
>>>E
^#>^
>>>^
```
输入#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####^<####^<
>>^<<<<<>>>>^<<<<<^<

说明/提示

样例 1 解释

在样例输出中， $d(2,3)=2$ ，并且沿着箭头格子 $(2,3)$ 需要恰好 $2$ 步到达安全出口。

其他所有空白格子也满足像这样的条件。

样例 2 解释

存在没有空白格子或安全出口的情况。

By @chenxi2009

输入解题思路，AI测评打分。不知道怎么写?

首页