B - Santa Claus 1 Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

縦 H 行横 W 列のマス目があります。上から i 行目、左から j 列目のマスをマス (i,j) と表します。

マス (i,j) は S_{i,j} が # のとき通行不可能、. のとき通行可能であり家が建っていない、@ のとき通行可能であり家が建っていることを表します。

最初、マス (X,Y) にサンタクロースがいます。サンタクロースは文字列 T に従って以下の行動を行います。

  • 文字列 T の長さを |T| とする。i=1,2,\ldots,|T| の順に以下のように移動する。
    • 現在サンタクロースがいるマスを (x,y) とする。
      • T_i が U かつマス (x-1,y) が通行可能ならマス (x-1,y) に移動する。
      • T_i が D かつマス (x+1,y) が通行可能ならマス (x+1,y) に移動する。
      • T_i が L かつマス (x,y-1) が通行可能ならマス (x,y-1) に移動する。
      • T_i が R かつマス (x,y+1) が通行可能ならマス (x,y+1) に移動する。
      • それ以外の場合、マス (x,y) に留まる。

行動を終えたあとにサンタクロースがいるマスと、行動により通過または到達した家の数を求めてください。ただし、同じ家を複数回通過または到達してもそれらは重複して数えません。

制約

  • 3 \leq H,W \leq 100
  • 1 \leq X \leq H
  • 1 \leq Y \leq W
  • 与えられる数値は全て整数である
  • S_{i,j} は #, ., @ のいずれか
  • 全ての 1 \leq i \leq H について S_{i,1},S_{i,W} は #
  • 全ての 1 \leq j \leq W について S_{1,j},S_{H,j} は #
  • S_{X,Y}= .
  • T は U, D, L, R のいずれかからなる長さ 1 以上 10^4 以下の文字列

入力

入力は以下の形式で標準入力から与えられる。

H W X Y
S_{1,1}S_{1,2}\ldots S_{1,W}
\dots
S_{H,1}S_{H,2}\ldots S_{H,W}
T

出力

行動を終えたあとサンタクロースがいるマスを (X,Y)、行動により通過または到達した家の数を C とするとき、X,Y,C をこの順に空白区切りで出力せよ。

入力例 1

5 5 3 4
#####
#...#
#.@.#
#..@#
#####
LLLDRUU

出力例 1

2 3 1

サンタクロースは以下のように行動します。

図

  • T_1= L なのでマス (3,4) からマス (3,3) に移動する。これにより家を通過する。
  • T_2= L なのでマス (3,3) からマス (3,2) に移動する。
  • T_3= L だがマス (3,1) は通行不可能なので、マス (3,2) に留まる。
  • T_4= D なのでマス (3,2) からマス (4,2) に移動する。
  • T_5= R なのでマス (4,2) からマス (4,3) に移動する。
  • T_6= U なのでマス (4,3) からマス (3,3) に移動する。これにより家を通過するが、この家はすでに通過したことがある家である。
  • T_7= U なのでマス (3,3) からマス (2,3) に移動する。

行動により通過または到達した家の数は 1 です。

入力例 2

6 13 4 6
#############
#@@@@@@@@@@@#
#@@@@@@@@@@@#
#@@@@.@@@@@@#
#@@@@@@@@@@@#
#############
UURUURLRLUUDDURDURRR

出力例 2

3 11 11

入力例 3

12 35 7 10
###################################
#.................................#
#..........@......................#
#......@................@.........#
#.............##............@.....#
#...##........##....##............#
#...##........##....##.......##...#
#....##......##......##....##.....#
#....##......##......##..##.......#
#.....#######.........###.........#
#.................................#
###################################
LRURRRUUDDULUDUUDLRLRDRRLULRRUDLDRU

出力例 3

4 14 1

Score : 200 points

Problem Statement

There is a grid with H rows and W columns. Let (i,j) denote the cell at the i-th row from the top and the j-th column from the left.

If S_{i,j} is #, the cell (i,j) is impassable; if it is ., the cell is passable and contains no house; if it is @, the cell is passable and contains a house.

Initially, Santa Claus is in cell (X,Y). He will act according to the string T as follows.

  • Let |T| be the length of the string T. For i=1,2,\ldots,|T|, he moves as follows.
    • Let (x,y) be the cell he is currently in.
      • If T_i is U and cell (x-1,y) is passable, move to cell (x-1,y).
      • If T_i is D and cell (x+1,y) is passable, move to cell (x+1,y).
      • If T_i is L and cell (x,y-1) is passable, move to cell (x,y-1).
      • If T_i is R and cell (x,y+1) is passable, move to cell (x,y+1).
      • Otherwise, stay in cell (x,y).

Find the cell where he is after completing all actions, and the number of distinct houses that he passed through or arrived at during his actions. If the same house is passed multiple times, it is only counted once.

Constraints

  • 3 \leq H,W \leq 100
  • 1 \leq X \leq H
  • 1 \leq Y \leq W
  • All given numbers are integers.
  • Each S_{i,j} is one of #, ., @.
  • S_{i,1} and S_{i,W} are # for every 1 \leq i \leq H.
  • S_{1,j} and S_{H,j} are # for every 1 \leq j \leq W.
  • S_{X,Y}= .
  • T is a string of length at least 1 and at most 10^4, consisting of U, D, L, R.

Input

The Input is given from Standard Input in the following format:

H W X Y
S_{1,1}S_{1,2}\ldots S_{1,W}
\dots
S_{H,1}S_{H,2}\ldots S_{H,W}
T

Output

Let (X,Y) be the cell where he is after completing all actions, and C be the number of distinct houses he passed through or arrived at during his actions. Print X,Y,C in this order separated by spaces.

Sample Input 1

5 5 3 4
#####
#...#
#.@.#
#..@#
#####
LLLDRUU

Sample Output 1

2 3 1

Santa Claus behaves as follows:

Figure

  • T_1= L, so he moves from (3,4) to (3,3). A house is passed.
  • T_2= L, so he moves from (3,3) to (3,2).
  • T_3= L, but cell (3,1) is impassable, so he stays at (3,2).
  • T_4= D, so he moves from (3,2) to (4,2).
  • T_5= R, so he moves from (4,2) to (4,3).
  • T_6= U, so he moves from (4,3) to (3,3). A house is passed, but it has already been passed.
  • T_7= U, so he moves from (3,3) to (2,3).

The number of houses he passed or arrived during his actions is 1.

Sample Input 2

6 13 4 6
#############
#@@@@@@@@@@@#
#@@@@@@@@@@@#
#@@@@.@@@@@@#
#@@@@@@@@@@@#
#############
UURUURLRLUUDDURDURRR

Sample Output 2

3 11 11

Sample Input 3

12 35 7 10
###################################
#.................................#
#..........@......................#
#......@................@.........#
#.............##............@.....#
#...##........##....##............#
#...##........##....##.......##...#
#....##......##......##....##.....#
#....##......##......##..##.......#
#.....#######.........###.........#
#.................................#
###################################
LRURRRUUDDULUDUUDLRLRDRRLULRRUDLDRU

Sample Output 3

4 14 1