T2 机器人巡逻（robot）

题目描述

科研人员在一块 $n$ 行 $m$ 列的网格上测试巡逻机器人。网格中 . 表示可以通行的格子，# 表示障碍物。

机器人从给定的起点格子出发，按照一个由指令组成的字符串依次移动，其中 U、D、L、R 分别表示向上、向下、向左、向右移动一格。如果某一步移动后会越界，或者目标格子是障碍物，则该步指令无效，机器人停留在原地不动；否则机器人移动到目标格子。

请你计算机器人执行完所有指令后，最终所在的位置，以及它一共经过了多少个不同的格子（起点也算经过一格）。

输入文件 robot.in，输出文件 robot.out。

输入格式

输入第一行包含两个正整数 $n,m$，表示网格的行数和列数。

接下来 $n$ 行，每行一个长度为 $m$ 的字符串，描述该网格，字符仅为 . 或 #。

下一行包含两个正整数 $sr, sc$，表示机器人起点在第 $sr$ 行第 $sc$ 列（行列均从 $1$ 开始编号）。

下一行包含一个字符串，表示机器人依次执行的指令。

输出格式

输出一行三个整数，依次表示机器人最终所在的行列 $r,c$，以及经过的不同格子数。

样例 1 输入

4 4
....
.##.
....
##..
1 1
RRDLLD

样例 1 输出

2 1 4

样例 1 解释

从 $(1,1)$ 出发：R 到 $(1,2)$，R 到 $(1,3)$；D 想走到 $(2,3)$ 但该格是障碍，停在 $(1,3)$；L 到 $(1,2)$，L 到 $(1,1)$；D 到 $(2,1)$。经过的不同格子为 $(1,1),(1,2),(1,3),(2,1)$，共 $4$ 个，最终停在 $(2,1)$。

样例 2 输入

3 3
...
.#.
...
1 1
RRRDDDLLLUUU

样例 2 输出

1 1 8

数据规模与约定

• 对于 $30\%$ 的数据，保证 $n,m \le 10$，指令长度不超过 $100$。
• 对于 $100\%$ 的数据，保证 $1 \le n,m \le 1000$，指令长度不超过 $10^6$，起点所在格子一定是 .。