#P18443. Palindrome Path

Palindrome Path

Palindrome Path

  • 标准输入、标准输出;单组数据。

题目描述

给定一个 n×mn\times m 的网格迷宫,每个格子 (i,j)(i,j) 为空格或障碍。George 现在位于起点 (sr,sc)(s_r,s_c),他需要访问迷宫中的所有空格,最后到达出口 (er,ec)(e_r,e_c)。

假设当前位于 (i,j)(i,j),他可以执行以下四种指令:

  1. 向左尝试移动,记作 L。如果 j>1j>1 且 (i,j−1)(i,j-1) 为空格,就移动到 (i,j−1)(i,j-1);否则停在原地。
  2. 向右尝试移动,记作 R。如果 j<mj<m 且 (i,j+1)(i,j+1) 为空格,就移动到 (i,j+1)(i,j+1);否则停在原地。
  3. 向上尝试移动,记作 U。如果 i>1i>1 且 (i−1,j)(i-1,j) 为空格,就移动到 (i−1,j)(i-1,j);否则停在原地。
  4. 向下尝试移动,记作 D。如果 i<ni<n 且 (i+1,j)(i+1,j) 为空格,就移动到 (i+1,j)(i+1,j);否则停在原地。

起点在操作开始之前就被视为已经访问。格子可以重复访问;被障碍或边界挡住的指令仍然是指令串中的一个字符。

为了增加趣味,他还要求整个指令串是回文串。形式化地,若指令为 M1,M2,…,MkM_1,M_2,\ldots,M_k,其中 $M_i\in\{\texttt{L},\texttt{R},\texttt{U},\texttt{D}\}$,则必须对每个 1≤i≤k1\le i\le k 都有 Mi=Mk−i+1M_i=M_{k-i+1}。

请找出一个回文指令串,使他访问所有空格并最终到达出口。若有多解,输出任意一个;若无解,报告无解。

输入格式

第一行包含两个整数 n,mn,m(1≤n,m≤301\le n,m\le30),表示迷宫的行数和列数。

接下来 nn 行,每行一个长度为 mm 的二进制字符串。第 ii 行第 jj 个字符为 1 表示 (i,j)(i,j) 是空格,为 0 表示障碍。

下一行四个整数 sr,sc,er,ecs_r,s_c,e_r,e_c(1≤sr,er≤n1\le s_r,e_r\le n,1≤sc,ec≤m1\le s_c,e_c\le m),表示起点与出口。

保证起点和出口均为空格。起点与出口可以相同。

输出格式

如果存在方案,在一行中输出指令字符串 SS,满足 0≤∣S∣≤1060\le |S|\le10^6;否则输出一行 -1。

如果不执行任何操作就已经完成目标,可以输出空字符串,但此时必须输出一个空行。不要在行尾添加额外空格,否则会得到 Wrong Answer。

原样例 1

输入:

2 2
11
11
1 1 2 2

输出:

RDLUULDR

该指令串的过程为:

  1. 从 (1,1)(1,1) 向右,移动到 (1,2)(1,2)。
  2. 向下,移动到 (2,2)(2,2)。
  3. 向左,移动到 (2,1)(2,1)。
  4. 向上,移动到 (1,1)(1,1)。
  5. 再向上,因已在第一行而停在 (1,1)(1,1)。
  6. 向左,因已在第一列而停在 (1,1)(1,1)。
  7. 向下,移动到 (2,1)(2,1)。
  8. 向右,移动到 (2,2)(2,2)。

所有空格均被访问,最终位置恰为出口 (2,2)(2,2)。

原样例 2

输入:

2 2
10
01
1 1 2 2

输出:

-1

第二个样例中,George 从 (1,1)(1,1) 无法到达 (2,2)(2,2),所以输出 -1。