删掉一条多余的路线指令

题目描述

记录的路线中多了一条命令，必须删除恰好一个位置。车从指定起点出发，依次执行剩下的U、D、L、R命令，每条命令必须实际移动一格；任何一步越界或进入#都令该删除方案无效。最终必须到达指定终点。求有多少个删除位置可行，以及最早位置。删除后为空命令串时，车停在起点。

输入格式

第一行H、W；随后H行网格；下一行起点行列、终点行列；最后一行命令串。 输入只有一组数据。

输出格式

输出可行删除位置数量及最早位置（从1开始）；没有可行方案输出0 -1。

样例 1

输入

1 3
...
1 1 1 3
RRR

输出

3 1

说明

三个删除位置分别计数。

样例 2

输入

1 1
.
1 1 1 1
UD

输出

0 -1

说明

删后仍有一步越界。

数据范围

• 1≤H,W≤10；命令长度1至80。
• 网格只含.与#；起点终点均为.。