/ 基础 / 题库 /

VOYAGER

VOYAGER

时间限制:1秒  内存限制:256M


题目描述

旅行者一号(Voyager 1)探测器(不要与 Intrepid 级星舰混淆)早在 1977 年就被发射升空,如今正接近离开我们的太阳系。在它不断穿梭于太空的旅途中,它被编程为在遇到的每一个恒星系统中留下无线电信号标记,以尽可能长时间地标记探测器的轨迹。

我们假设一个恒星系统可以用一个 \(N\) 行 \(M\) 列的矩形网格表示,将空间划分为 \(N \times M\) 个相等的格子。每个格子可以包含一个行星、黑洞,或者为空。探测器会从一个预定的空格子中,以某个轴对齐的方向("U"-上,"R"-右,"D"-下,"L"-左)发出信号。

信号发射后,会沿当前行/列的直线方向传播,直到遇到行星,此时信号会被偏转 \(90\) 度,转向另一个方向。有两种类型的行星,分别用 "/" 和 "\" 表示。偏转规则如下图所示:

说明

当信号进入黑洞格子,或离开矩形网格边界时,信号会永久离开该系统。已知信号从当前格子传播到相邻格子需要 \(1\) 秒。

请编写程序,确定探测器应以哪个方向发射信号,才能使信号在系统中停留的时间最长,并输出最佳方向以及最长停留时间。如果信号可以在系统内无限循环,请输出 "Voyager" 替代时间。

输入格式

第一行输入两个正整数 \(N\)(\(1 \leq N \leq 500\))和 \(M\)(\(1 \leq M \leq 500\))。

接下来 \(N\) 行,每行 \(M\) 个字符,字符集为 /, \, C, .,其中 "/" 和 "\" 表示两种类型的行星,"C" 表示黑洞,"." 表示空格子。

最后一行输入两个正整数 \({PR}\)(\(1 \leq PR \leq N\))和 \({PC}\)(\(1 \leq {PC} \leq {M}\)),分别表示探测器所在格子的行号和列号。

输出格式

输出两行。

第一行输出最佳发射方向("U"、"R"、"D"、"L")。如果有多种方案,按以下优先顺序输出:先 "U",再 "R",然后 "D",最后 "L"。

第二行输出最长停留时间(或 "Voyager")。

输入输出样例 #1

输入 #1

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

输出 #1

U
17

输入输出样例 #2

输入 #2

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

输出 #2

D
12

输入输出样例 #3

输入 #3

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

输出 #3

R
Voyager

说明/提示

在价值至少 50% 分数的测试数据中,信号不可能在系统内无限循环。

第一个样例的说明("*" 表示信号的路径):
说明

信息

ID
1050
难度
(无)
分类
(无)
标签
(无)
递交数
0
已通过
0
通过率
?
被复制
1
上传者