QOJ.ac

QOJ

Límite de tiempo: 1.0 s Límite de memoria: 32 MB Puntuación total: 90

#16639. 旅行者

Estadísticas

旅行者 1 号太空探测器(不要与无畏级星舰混淆)很久以前于 1977 年发射,目前正处于离开太阳系的边缘。随着它在太空中进一步航行,它被程序设定为在它遇到的任何恒星系统中留下无线电信号信息,以尽可能长地标记探测器的路径。

让我们假设一个恒星系统可以用一个具有 $N$ 行 and $M$ 列的矩形网格表示,将空间划分为 $N \times M$ 个相等的单元格。每个单元格可以包含一个行星、一个黑洞,或者为空。探测器从一个预先确定的空单元格向四个轴对齐的方向之一(“U”表示上,“R”表示右,“D”表示下,“L”表示左)广播信号。

广播后,信号沿同一行/列呈直线传播,直到到达一颗行星,在那里它会被偏转 90 度到另一个方向。有两种行星,我们分别用 /\ 表示。偏转规则如下图所示:

当信号进入包含黑洞的单元格,或传播到矩形网格边界之外时,信号将永久离开系统。已知信号从当前单元格传播到相邻单元格需要 $1$ 秒。

编写一个程序,确定探测器需要广播信号的方向,使信号在系统内停留的时间尽可能长,输出最优方向以及相应的最长时间。如果信号可以无限期地留在系统中,则输出 “Voyager” 代替所需的时间。

输入格式

输入的第一行包含两个正整数 $N$($1 \le N \le 500$)和 $M$($1 \le M \le 500$)。

接下来的 $N$ 行中,每行包含 $M$ 个来自字符集 {"/", "\", "C", "."} 的字符,其中 /\ 代表两种行星,C 代表黑洞,. 代表空单元格。

最后一行包含两个正整数 $PR$($1 \le PR \le N$)和 $PC$($1 \le PC \le M$),分别代表探测器所在单元格的行号和列号。

输出格式

输出的第一行必须包含所需的最佳广播方向(“U”、“R”、“D” 或 “L”)。如果解不唯一,请按照以下优先级顺序选择第一个最优解:首先是 “U”,然后是 “R”,接着是 “D”,最后是 “L”。

输出的第二行必须包含所需的最长时间(或信息)。

子任务

在价值至少 50% 总分的测试数据中,信号将无法无限期地留在系统中。

样例

输入格式 1

5 5
../.\
.....
.C...
...C.
\.../
3 3

输出格式 1

U
17

输入格式 2

5 5
....\
\..\.
./\..
\../C
.\../
1 1

输出格式 2

D
12

输入格式 3

5 7
/.....\
../..\.
\...../
/.....\
\.\.../
3 3

输出格式 3

R
Voyager

说明

第一个样例的解释(* 代表信号的路径):

起点           'U' 方向         'R' 方向         'D' 方向         'L' 方向
../.\          *.***            ../.\            ../.\            ../.\
.....          *.*.*            .....            .....            .....
.CS..          *C*.*            .C***            .C*..            .C*..
...C.          *..C*            ...C.            ..*C.            ...C.
\.../          *****            \.../            \.*./            \.../

               17 秒            3 秒             3 秒             1 秒

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.