← 返回题目列表

AtCoder · abc385_b

C. 圣诞老人 1

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

分数: 200 点

问题陈述

有一个网格 H 行和 W 列。让 (i,j) 表示位于 i从顶部开始的第行和 j左起第 列。

If S_{i,j} is #,单元格 (i,j) 无法通行;如果是的话 .,该小区可通行且不含房屋;如果是的话 @,该牢房可以通过并且包含一座房子。

最初,圣诞老人在牢房里 (X,Y)。他会按照弦来行动 T 如下。

  • 让 |T| 是字符串的长度 T。对于 i=1,2,\ldots,|T|,他的动作如下。
    • 让 (x,y) 是他当前所在的牢房。
      • If T_i is U 和细胞 (x-1,y) 还可以,移至单元格 (x-1,y).
      • If T_i is D 和细胞 (x+1,y) 还可以,移至单元格 (x+1,y).
      • If T_i is L 和细胞 (x,y-1) 还可以,移至单元格 (x,y-1).
      • If T_i is 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} 是其中之一 #, ., @.
  • S_{i,1} 和 S_{i,W} 是 # 对于每个 1 \leq i \leq H.
  • S_{1,j} 和 S_{H,j} 是 # 对于每个 1 \leq j \leq W.
  • S_{X,Y}= .
  • T 是长度至少为 1 最多 10^4,包括 U, D, L, R.

输入

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

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

圣诞老人的行为如下:

Figure

  • T_1= L,所以他从 (3,4) to (3,3)。一座房子过去了。
  • T_2= L,所以他从 (3,3) to (3,2).
  • T_3= L,但是单元格 (3,1) 无法通行,所以他留在 (3,2).
  • T_4= D,所以他从 (3,2) to (4,2).
  • T_5= R,所以他从 (4,2) to (4,3).
  • T_6= U,所以他从 (4,3) to (3,3)。一座房子过去了,但它已经过去了。
  • T_7= U,所以他从 (3,3) to (2,3).

他的行动中经过或到达的房屋数量为 1.


示例输入 2

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

示例输出 2

3 11 11

示例输入 3

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

示例输出 3

4 14 1