U211827 [COCI2012-2013#4] VOYAGER

[旅行者 1 号太空探测器](https://en.wikipedia.org/wiki/Voyager_1)在很久以前的 1977 年 9 月 5 日发射。截至 2019 年 10 月 23 日，旅行者 1 号正处于离太阳 211 亿公里的距离。当它在太空中进一步行进时，它已按照即定程序在它偶然发现的任何恒星系统中留下无线电信号信息，以尽可能长时间地标记探测器的路径。

让我们假定一个恒星星系可以用一个 $n$ 行 $m$ 列的网格图表示。每个网格要么包含一个星球，要么包含一个黑洞，要么是空的。旅行者 1 号从一个预先确定的**空的**网格上，以上下左右中的一个方向作为初始方向开始运动，并向地面播报其运动轨迹。 在播报的同时，旅行者 1 号会沿着同一行 / 列直线运动，直到到达一个星球。此时，旅行者 1 号将会向另一个方向偏转 $90$ 度后继续沿直线运动。该恒星星系中有两种星球，我们将其用 `/` 或 `\` 表示。其偏转规则如下图所示：  旅行者 1 号在进入包含黑洞的网格或者运动出星系边际后将会在地面信号中消失。已知旅行者 1 号从一个网格运动到另一个网格上需要花费 $1$ 秒时间。 现在，给定你 $n$ 行 $m$ 列的网格图，请你确定旅行者 1 号的初始运动方向，使得其在星系中的运动时间尽可能长。

第一行输入两个整数 $n,m$，表示网格图的行数和列数。 随后 $n$ 行，每行输入一个长度为 $m$ 的字符串，描述网格图上所有的网格。其中，`C` 表示该网格包含一个黑洞，`\` 或 `/` 表示该网格包含一个星球（具体含义见『题目描述』部分），`.` 表示该网格为空。 随后一行输入两个整数 $r,c$，表示旅行者 1 号的初始位置。

第一行输出一个字符（`U`、`D`、`L`、`R` 四个字符中的一个），表示旅行者 1 号的初始运动方向。具体地，`U` 表示上，`D` 表示下，`L` 表示左，`R` 表示右。 第二行输出一个整数，表示旅行者 1 号在星系内的运动时间的最大值。如果旅行者 1 号将永远在星系内运动，则在该行输出 `Voyager`。 如果有多个方向满足要求，按照优先级从从先到后依次为 `U`、`R`、`D`、`L` 的顺序选择第一个最佳选项。

**【样例 1 解释】** 一开始旅行者 1 号在网格图上的位置如下（标记为 `S`）： ``` ../.\ ..... .CS.. ...C. \.../ ``` 下图从左往右依次给出了旅行者 1 号初始方向在上、右、下、左时的运动轨迹：  可以发现，当旅行者 1 号初始方向为上时，在星系中的运动时间最长，为 $17$ 秒。 **【数据范围及限制】** **本题开启捆绑测试**。各个子任务的特殊限制如下： - Subtask 1（45 pts）：不存在使得旅行者 1 号永远在星系内运动的初始方向。 - Subtask 2（45 pts）：无特殊限制。 对于所有数据，$1\leqslant n,m\leqslant 500$，$1\leqslant r\leqslant n$，$1\leqslant c\leqslant m$。 **【题目来源】** 本题来源自 **_[COCI 2012-2013](https://hsin.hr/coci/archive/2012_2013/) [CONTEST 4](https://hsin.hr/coci/archive/2012_2013/contest4_tasks.pdf) T3 VOYAGER_**，按照原题数据配置，满分 $90$ 分。 由 [Eason_AC](https://www.luogu.com.cn/user/112917) 翻译整理提供。