障碍网格机器人

题目描述

给定一个 n × m 的网格：

• . 表示可以经过的空地；
• # 表示障碍物。

机器人初始位于 (sx,sy)，坐标从 1 开始。随后机器人依次执行一串指令：

• U：向上移动一格；
• D：向下移动一格；
• L：向左移动一格；
• R：向右移动一格。

若下一格越界或为障碍物，则本条指令无效，机器人保持原位。请输出全部指令执行后的最终位置。

输入格式

第一行两个整数 n、m。

接下来 n 行，每行一个长度为 m 的字符串，表示网格。

下一行两个整数 sx、sy。

下一行一个整数 q，表示指令数量。

最后一行一个长度为 q 的字符串，只包含 U、D、L、R。

输出格式

输出两个整数，表示机器人最终所在的行和列。

3 4
....
.##.
....
1 1
8
RRDDLLUU

1 1

数据范围

• 1 <= n,m <= 500
• 1 <= q <= 200000
• 初始位置一定是空地