B - Warehouse Inspection Robot Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 266 点

問題文

高橋君は H 行 W 列のグリッド状の倉庫を管理しています。上から i 行目 (1 \leq i \leq H)、左から j 列目 (1 \leq j \leq W) のマスをマス (i, j) と表します。各マスには荷物が置かれているか、何もないかのどちらかです。倉庫の状態は H 個の長さ W の文字列 S_1, S_2, \ldots, S_H で表され、S_i の j 文字目が # ならマス (i, j) に荷物が置かれており、. なら何もないことを意味します。

高橋君はこの倉庫に点検ロボットを 1 台導入し、ロボットを動かすことで荷物の回収をしようと考えています。ロボットは最初、マス (1, 1)（左上隅）に配置されます。

ロボットには長さ N の文字列 T で表される N 個の命令が順番に与えられます。T の k 文字目 (1 \leq k \leq N) が k 番目の命令に対応し、各命令は以下のいずれかです。

  • U：上に 1 マス移動する（行番号が 1 減る方向）
  • D：下に 1 マス移動する（行番号が 1 増える方向）
  • L：左に 1 マス移動する（列番号が 1 減る方向）
  • R：右に 1 マス移動する（列番号が 1 増える方向）

ただし、命令による移動先がグリッドの外になる場合、その命令は無視され、ロボットはその場に留まります。

ロボットの動作は以下の流れで処理されます。

  1. ロボットがマス (1, 1) に配置される。マス (1, 1) に荷物があれば、回収される（そのマスの荷物がなくなる）。
  2. k = 1, 2, \ldots, N の順に、k 番目の命令を実行する。各命令の処理後（移動した場合も、命令が無視されてその場に留まった場合も）、ロボットがいるマスに荷物があれば、回収される（そのマスの荷物がなくなる）。

すでに荷物が回収されたマスを再び訪れても何も起きません。

すべての命令を実行し終えた後、倉庫に残っている荷物の個数を求めてください。

制約

  • 1 \leq H \leq 500
  • 1 \leq W \leq 500
  • 1 \leq N \leq 2 \times 10^5
  • H, W, N は整数
  • S_i は長さ W の文字列で、# と . のみからなる
  • T は長さ N の文字列で、U, D, L, R のみからなる

入力

H W N
S_1
S_2
\vdots
S_H
T
  • 1 行目には、倉庫の行数 H、列数 W、命令の数 N が、スペース区切りで与えられます。
  • 2 行目から H + 1 行目には、倉庫の状態を表す文字列 S_i (1 \leq i \leq H) が与えられます。
  • S_i は長さ W の文字列で、j 文字目が # ならマス (i, j) に荷物が置かれており、. なら何もないことを表します。
  • H + 2 行目には、ロボットへの命令を表す長さ N の文字列 T が与えられます。
  • T は U, D, L, R のみからなります。

出力

すべての命令を実行し終えた後に倉庫に残っている荷物の個数を 1 行で出力してください。

入力例 1

3 4 9
#..#
.##.
..#.
RRDDLUUUL

出力例 1

1

入力例 2

2 3 8
###
..#
UUURRRDD

出力例 2

0

入力例 3

6 7 30
.#..#..
##...#.
..#.#..
.##....
...###.
#..#..#
RRRDDRULDLURRRDDLLUUURRDDDLURD

出力例 3

10

入力例 4

12 15 60
#..#...##....#.
.#....#....##..
....##..#...#..
###...#..#.....
..#..#..##..#..
.....#.....#..#
.##..#..#..##..
...#.....##....
#....###...#...
..##..#....#..#
.#...#..#..#...
...#..##.....#.
RRDDLLUUURRRDDLLUUURRRDDLLUUURRRDDLLUUURRRDDLLUUURRRDDLLUUUR

出力例 4

46

入力例 5

1 1 12
#
UDLRUDLRUDLR

出力例 5

0

Score : 266 pts

Problem Statement

Takahashi manages a warehouse in the form of a grid with H rows and W columns. The cell at the i-th row from the top (1 \leq i \leq H) and the j-th column from the left (1 \leq j \leq W) is denoted as cell (i, j). Each cell either has a package placed on it or is empty. The state of the warehouse is represented by H strings S_1, S_2, \ldots, S_H, each of length W. If the j-th character of S_i is #, then cell (i, j) has a package; if it is ., the cell is empty.

Takahashi plans to introduce one inspection robot into this warehouse and have it collect packages by moving around. The robot is initially placed at cell (1, 1) (the top-left corner).

The robot is given N instructions in order, represented by a string T of length N. The k-th character of T (1 \leq k \leq N) corresponds to the k-th instruction, and each instruction is one of the following:

  • U: Move one cell up (row number decreases by 1)
  • D: Move one cell down (row number increases by 1)
  • L: Move one cell left (column number decreases by 1)
  • R: Move one cell right (column number increases by 1)

However, if the destination of an instruction would be outside the grid, that instruction is ignored, and the robot stays in its current position.

The robot operates as follows:

  1. The robot is placed at cell (1, 1). If cell (1, 1) has a package, it is collected (the package is removed from that cell).
  2. For k = 1, 2, \ldots, N in order, the k-th instruction is executed. After processing each instruction (whether the robot moved or the instruction was ignored and the robot stayed in place), if there is a package on the cell where the robot is located, it is collected (the package is removed from that cell).

If the robot revisits a cell from which a package has already been collected, nothing happens.

Determine the number of packages remaining in the warehouse after all instructions have been executed.

Constraints

  • 1 \leq H \leq 500
  • 1 \leq W \leq 500
  • 1 \leq N \leq 2 \times 10^5
  • H, W, N are integers
  • S_i is a string of length W consisting only of # and .
  • T is a string of length N consisting only of U, D, L, R

Input

H W N
S_1
S_2
\vdots
S_H
T
  • The first line contains the number of rows H, the number of columns W, and the number of instructions N, separated by spaces.
  • The 2-nd through (H + 1)-th lines contain the strings S_i (1 \leq i \leq H) representing the state of the warehouse.
  • S_i is a string of length W, where the j-th character being # means cell (i, j) has a package, and . means it is empty.
  • The (H + 2)-th line contains the string T of length N representing the instructions to the robot.
  • T consists only of U, D, L, R.

Output

Print the number of packages remaining in the warehouse after all instructions have been executed, on a single line.

Sample Input 1

3 4 9
#..#
.##.
..#.
RRDDLUUUL

Sample Output 1

1

Sample Input 2

2 3 8
###
..#
UUURRRDD

Sample Output 2

0

Sample Input 3

6 7 30
.#..#..
##...#.
..#.#..
.##....
...###.
#..#..#
RRRDDRULDLURRRDDLLUUURRDDDLURD

Sample Output 3

10

Sample Input 4

12 15 60
#..#...##....#.
.#....#....##..
....##..#...#..
###...#..#.....
..#..#..##..#..
.....#.....#..#
.##..#..#..##..
...#.....##....
#....###...#...
..##..#....#..#
.#...#..#..#...
...#..##.....#.
RRDDLLUUURRRDDLLUUURRRDDLLUUURRRDDLLUUURRRDDLLUUURRRDDLLUUUR

Sample Output 4

46

Sample Input 5

1 1 12
#
UDLRUDLRUDLR

Sample Output 5

0