#P18443. Palindrome Path
Palindrome Path
Palindrome Path
- 标准输入、标准输出;单组数据。
题目描述
给定一个 的网格迷宫,每个格子 为空格或障碍。George 现在位于起点 ,他需要访问迷宫中的所有空格,最后到达出口 。
假设当前位于 ,他可以执行以下四种指令:
- 向左尝试移动,记作
L。如果 且 为空格,就移动到 ;否则停在原地。 - 向右尝试移动,记作
R。如果 且 为空格,就移动到 ;否则停在原地。 - 向上尝试移动,记作
U。如果 且 为空格,就移动到 ;否则停在原地。 - 向下尝试移动,记作
D。如果 且 为空格,就移动到 ;否则停在原地。
起点在操作开始之前就被视为已经访问。格子可以重复访问;被障碍或边界挡住的指令仍然是指令串中的一个字符。
为了增加趣味,他还要求整个指令串是回文串。形式化地,若指令为 ,其中 $M_i\in\{\texttt{L},\texttt{R},\texttt{U},\texttt{D}\}$,则必须对每个 都有 。
请找出一个回文指令串,使他访问所有空格并最终到达出口。若有多解,输出任意一个;若无解,报告无解。
输入格式
第一行包含两个整数 (),表示迷宫的行数和列数。
接下来 行,每行一个长度为 的二进制字符串。第 行第 个字符为 1 表示 是空格,为 0 表示障碍。
下一行四个整数 (,),表示起点与出口。
保证起点和出口均为空格。起点与出口可以相同。
输出格式
如果存在方案,在一行中输出指令字符串 ,满足 ;否则输出一行 -1。
如果不执行任何操作就已经完成目标,可以输出空字符串,但此时必须输出一个空行。不要在行尾添加额外空格,否则会得到 Wrong Answer。
原样例 1
输入:
2 2
11
11
1 1 2 2
输出:
RDLUULDR
该指令串的过程为:
- 从 向右,移动到 。
- 向下,移动到 。
- 向左,移动到 。
- 向上,移动到 。
- 再向上,因已在第一行而停在 。
- 向左,因已在第一列而停在 。
- 向下,移动到 。
- 向右,移动到 。
所有空格均被访问,最终位置恰为出口 。
原样例 2
输入:
2 2
10
01
1 1 2 2
输出:
-1
第二个样例中,George 从 无法到达 ,所以输出 -1。