#ABC385B. 圣诞老人

圣诞老人

AT_abc385_b [ABC385B] Santa Claus 1

题目描述

\hspace{15pt}有一个 hh 行 ww 列的网格。用 (i,j)(i, j) 表示从上往下数第 ii 行、从左往右数第 jj 列的单元格。

\hspace{15pt}如果 si,js_{i,j} 是 ‘#’\texttt{`\#'},则单元格 (i,j)(i, j) 不可通过;如果是 ‘.’\texttt{`.'},则该单元格可以通过且没有房子;如果是 ‘@’\texttt{`@'},则该单元格可以通过且有一个房子。

\hspace{15pt}最初,圣诞老人在单元格 (x0,y0)(x_0, y_0) 中。他将按照字符串 tt 的指示依次行动。设 ∣t∣|t| 为字符串 tt 的长度,对于 i=1,2,…,∣t∣i = 1, 2, \dots, |t|,第 ii 次行动的过程如下:

∙ \hspace{23pt}\bullet\,记 (x,y)(x, y) 为他当前所在的单元格;

∙ \hspace{23pt}\bullet\,若 ti=‘U’t_i = \texttt{`U'} 且单元格 (x−1,y)(x-1, y) 可通过,则他移动到单元格 (x−1,y)(x-1, y);

∙ \hspace{23pt}\bullet\,若 ti=‘D’t_i = \texttt{`D'} 且单元格 (x+1,y)(x+1, y) 可通过,则他移动到单元格 (x+1,y)(x+1, y);

∙ \hspace{23pt}\bullet\,若 ti=‘L’t_i = \texttt{`L'} 且单元格 (x,y−1)(x, y-1) 可通过,则他移动到单元格 (x,y−1)(x, y-1);

∙ \hspace{23pt}\bullet\,若 ti=‘R’t_i = \texttt{`R'} 且单元格 (x,y+1)(x, y+1) 可通过,则他移动到单元格 (x,y+1)(x, y+1);

∙ \hspace{23pt}\bullet\,否则,他停留在单元格 (x,y)(x, y)。

\hspace{15pt}请找出他完成所有行动后所在的单元格,以及他在行动过程中经过或到达的不同房子的数量。如果多次经过同一个房子,只计数一次。

输入格式

\hspace{15pt}第一行输入四个整数 $h, w, x_0, y_0 \left(3 \leqq h, w \leqq 100;\ 1 \leqq x_0 \leqq h;\ 1 \leqq y_0 \leqq w\right)$,依次代表网格的行数、列数,以及圣诞老人初始所在单元格的行号和列号。

\hspace{15pt}此后 hh 行,第 ii 行输入一个长度为 ww、仅由 ‘#’\texttt{`\#'}、‘.’\texttt{`.'} 和 ‘@’\texttt{`@'} 构成的字符串 sis_i,描述网格第 ii 行的状态。

\hspace{15pt}最后一行输入一个长度至少为 11、至多为 10410^4,且仅由 ‘U’\texttt{`U'}、‘D’\texttt{`D'}、‘L’\texttt{`L'} 和 ‘R’\texttt{`R'} 构成的字符串 tt,代表圣诞老人的行动序列。

\hspace{15pt}保证对于每个 1≦i≦h1 \leqq i \leqq h,si,1s_{i,1} 和 si,ws_{i,w} 均为 ‘#’\texttt{`\#'};对于每个 1≦j≦w1 \leqq j \leqq w,s1,js_{1,j} 和 sh,js_{h,j} 均为 ‘#’\texttt{`\#'}。特别地,sx0,y0=‘.’s_{x_0,y_0} = \texttt{`.'}。

输出格式

\hspace{15pt}设 (x1,y1)(x_1, y_1) 为他完成所有行动后所在的单元格,cc 为他在行动过程中经过或到达的不同房子的数量。在一行上输出三个整数 x1,y1,cx_1, y_1, c,相邻两个整数之间用一个空格隔开。

测试样例

5 5 3 4
#####
#...#
#.@.#
#..@#
#####
LLLDRUU
2 3 1
6 13 4 6
#############
#@@@@@@@@@@@#
#@@@@@@@@@@@#
#@@@@.@@@@@@#
#@@@@@@@@@@@#
#############
UURUURLRLUUDDURDURRR
3 11 11
12 35 7 10
###################################
#.................................#
#..........@......................#
#......@................@.........#
#.............##............@.....#
#...##........##....##............#
#...##........##....##.......##...#
#....##......##......##....##.....#
#....##......##......##..##.......#
#.....#######.........###.........#
#.................................#
###################################
LRURRRUUDDULUDUUDLRLRDRRLULRRUDLDRU
4 14 1

样例 1 解释

\hspace{15pt}圣诞老人的行动过程如下:

∙ \hspace{23pt}\bullet\,当 t1=‘L’t_1 = \texttt{`L'} 时,他从 (3,4)(3, 4) 移动到 (3,3)(3, 3),经过了一个房子;

∙ \hspace{23pt}\bullet\,当 t2=‘L’t_2 = \texttt{`L'} 时,他从 (3,3)(3, 3) 移动到 (3,2)(3, 2);

∙ \hspace{23pt}\bullet\,当 t3=‘L’t_3 = \texttt{`L'} 时,单元格 (3,1)(3, 1) 不可通过,所以他停留在 (3,2)(3, 2);

∙ \hspace{23pt}\bullet\,当 t4=‘D’t_4 = \texttt{`D'} 时,他从 (3,2)(3, 2) 移动到 (4,2)(4, 2);

∙ \hspace{23pt}\bullet\,当 t5=‘R’t_5 = \texttt{`R'} 时,他从 (4,2)(4, 2) 移动到 (4,3)(4, 3);

∙ \hspace{23pt}\bullet\,当 t6=‘U’t_6 = \texttt{`U'} 时,他从 (4,3)(4, 3) 移动到 (3,3)(3, 3),经过了一个房子,但这个房子之前已经经过过;

∙ \hspace{23pt}\bullet\,当 t7=‘U’t_7 = \texttt{`U'} 时,他从 (3,3)(3, 3) 移动到 (2,3)(2, 3)。

\hspace{15pt}他最终位于单元格 (2,3)(2, 3),行动过程中经过或到达的不同房子的数量为 11。