题目描述

在一个 $n \times m$（$n,m \le 150$）的网格上，有一些格子是障碍的，并且网格边界上的格子均是障碍的，另有一个非障碍的格子是出口。一个机器人可以根据程序在该网格上行走。一段程序是一个由 $\tt UDLR$ 四种指令组成的字符串，机器人会依次执行每个命令，一个指令会使机器人向指定的方向移动一格，如果对应的格子为障碍则不动，现在给定一格长度为 $l$（$l \le 10^5$）的程序，求它的一个最短前缀 $p$，使得对于一开始的网格上任意非障碍位置都是机器人，在执行完程序 $p$ 之后都停在出口上。

输入格式

第一行包含三个整数 $n,m,l$。

接下来是一个 $n \times m$ 的网格，# 表示障碍，. 表示可以走，E 表示出口。

最后一行是一个长度为 $l$ 的指令序列。

输出格式

一个整数表示答案。若不存在最短前缀 $p$ 能够满足要求，则输出 -1。

5 5 7
#####
#...#
#...#
#E..#
#####
UULLDDR

6

5 5 7
#####
#.#.#
#...#
#E..#
#####
UULLDDR

-1

5 3 2
###
#.#
#.#
#E#
###
DD

2