问题2669--LHX迷路了

2669: LHX迷路了

[命题人 : ]
时间限制 : 6 sec  内存限制 : 128 MB

提交
解决: 10提交量: 46统计

题目描述

LHX有一个 H×W 的网格，其中 . 代表陆地，# 代表海洋，LHX只能在陆地上行走。

LHX坠落到了一个陆地上，现在有一个长度为N的字符串T，接着他会依次沿着给定的字符串 T 进行移动，其中字符串中的 LRUD，分别表示向左、向右、向上、向下移动一个单元格。

你不知道 LHX 坠落的位置，所以请求出 LHX 移动后可能的位置数量。
H、W 和 N 为整数。
3 ≤ H,W ≤ 500
1 ≤ N ≤ 500 T 是长度为 N 的字符串，由 L、R、U 和 D 组成。
Si 是长度为 W 的字符串，由 . 和 # 组成。
至少有一个单元格可能是 LHX 的当前位置。
网格周边的所有单元格都是海洋。


输入

H W N
T 
S1 
S2 
.
.
.
SH 

输出

输出答案。

样例输入 Copy 

6 7 5
LULDR
#######
#...#.#
##...##
#.#...#
#...#.#
#######

样例输出 Copy 

2

提示

以下两种情况是可能的，因此有两个单元格可能是高桥的当前位置： (3,4)和 (4,5)。

  • 他坠毁在单元格 (3,5)(3,5) 上并移动了 (3,5)→(3,4)→(2,4)→(2,3)→(3,3)→(3,4)
  • 他坠毁在单元格 (4,6)(4,6) 上并移动了 (4,6)→(4,5)→(3,5)→(3,4)→(4,4)→(4,5)

来源/分类

 
提交