← 返回题目列表

AtCoder · abc341_c

F. 高桥迷路了

中文机器翻译题面 查看原题

分数: 250 点

问题陈述

有一个网格 H 行和 W 列。

网格的每个单元格是 土地 or 海,表示为 H 字符串 S_1, S_2, \ldots, S_H 长度 W。让 (i, j) 表示位于 i从顶部开始的第行和 j从左边算起第 3 列,以及 (i, j) 是土地,如果 如果字符是 j- 第一个字符 S_i is .,和 (i, j) 是海 #.

约束保证网格周边的所有单元格(即单元格 (i, j) 满足至少一项 i = 1, i = H, j = 1, j = W)是大海。

高桥的宇宙飞船坠毁在网格中的一个单元格上。后来他搬家了 按照字符串表示的指令在网格上 N 次 T 长度 N 组成 L, R, U,和 D。对于 i = 1, 2, \ldots, N, i- 第一个字符 T 描述了 i第一步移动如下:

  • L 表示向左移动一个单元格。也就是说,如果他在 (i, j) 搬迁之前,他将在 (i, j-1) 移动后。
  • R 表示向右移动一个单元格。也就是说,如果他在 (i, j) 搬迁之前,他将在 (i, j+1) 移动后。
  • U 表示向上移动一个单元格。也就是说,如果他在 (i, j) 搬迁之前,他将在 (i-1, j) 移动后。
  • D 表示向下移动一个单元格。也就是说,如果他在 (i, j) 搬迁之前,他将在 (i+1, j) 移动后。

众所周知,他沿途的所有单元格(包括他迫降的单元格和他当前所在的单元格)都不是海洋。打印可能是他当前位置的单元格数量。

约束

  • H, W,和 N 是整数。
  • 3 \leq H, W \leq 500
  • 1 \leq N \leq 500
  • T 是一个长度为的字符串 N 组成 L, R, U,和 D.
  • S_i 是一个长度为的字符串 W 组成 . 和 #.
  • 至少有一个单元格可能是高桥的当前位置。
  • 网格周边的所有单元格都是海洋。

输入

输入由标准输入按以下格式给出:

H W N
T
S_1
S_2
\vdots
S_H

输出

打印答案。


示例输入 1

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

示例输出 1

2

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

  • 他坠毁在手机上 (3, 5) 并搬家 (3, 5) \rightarrow (3, 4) \rightarrow (2, 4) \rightarrow (2, 3) \rightarrow (3, 3) \rightarrow (3, 4).
  • 他坠毁在手机上 (4, 6) 并搬家 (4, 6) \rightarrow (4, 5) \rightarrow (3, 5) \rightarrow (3, 4) \rightarrow (4, 4) \rightarrow (4, 5).

示例输入 2

13 16 9
ULURDLURD
################
##..##.#..####.#
###.#..#.....#.#
#..##..#####.###
#...#..#......##
###.##.#..#....#
##.#####....##.#
###.###.#.#.#..#
######.....##..#
#...#.#.######.#
##..###..#..#.##
#...#.#.#...#..#
################

示例输出 2

6