AT_abc385_b [ABC385B] Santa Claus 1
题目描述
有一个 h 行 w 列的网格。用 (i,j) 表示从上往下数第 i 行、从左往右数第 j 列的单元格。
如果 si,j 是 ‘#’,则单元格 (i,j) 不可通过;如果是 ‘.’,则该单元格可以通过且没有房子;如果是 ‘@’,则该单元格可以通过且有一个房子。
最初,圣诞老人在单元格 (x0,y0) 中。他将按照字符串 t 的指示依次行动。设 ∣t∣ 为字符串 t 的长度,对于 i=1,2,…,∣t∣,第 i 次行动的过程如下:
∙记 (x,y) 为他当前所在的单元格;
∙若 ti=‘U’ 且单元格 (x−1,y) 可通过,则他移动到单元格 (x−1,y);
∙若 ti=‘D’ 且单元格 (x+1,y) 可通过,则他移动到单元格 (x+1,y);
∙若 ti=‘L’ 且单元格 (x,y−1) 可通过,则他移动到单元格 (x,y−1);
∙若 ti=‘R’ 且单元格 (x,y+1) 可通过,则他移动到单元格 (x,y+1);
∙否则,他停留在单元格 (x,y)。
请找出他完成所有行动后所在的单元格,以及他在行动过程中经过或到达的不同房子的数量。如果多次经过同一个房子,只计数一次。
输入格式
第一行输入四个整数 $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)$,依次代表网格的行数、列数,以及圣诞老人初始所在单元格的行号和列号。
此后 h 行,第 i 行输入一个长度为 w、仅由 ‘#’、‘.’ 和 ‘@’ 构成的字符串 si,描述网格第 i 行的状态。
最后一行输入一个长度至少为 1、至多为 104,且仅由 ‘U’、‘D’、‘L’ 和 ‘R’ 构成的字符串 t,代表圣诞老人的行动序列。
保证对于每个 1≦i≦h,si,1 和 si,w 均为 ‘#’;对于每个 1≦j≦w,s1,j 和 sh,j 均为 ‘#’。特别地,sx0,y0=‘.’。
输出格式
设 (x1,y1) 为他完成所有行动后所在的单元格,c 为他在行动过程中经过或到达的不同房子的数量。在一行上输出三个整数 x1,y1,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 解释
圣诞老人的行动过程如下:
∙当 t1=‘L’ 时,他从 (3,4) 移动到 (3,3),经过了一个房子;
∙当 t2=‘L’ 时,他从 (3,3) 移动到 (3,2);
∙当 t3=‘L’ 时,单元格 (3,1) 不可通过,所以他停留在 (3,2);
∙当 t4=‘D’ 时,他从 (3,2) 移动到 (4,2);
∙当 t5=‘R’ 时,他从 (4,2) 移动到 (4,3);
∙当 t6=‘U’ 时,他从 (4,3) 移动到 (3,3),经过了一个房子,但这个房子之前已经经过过;
∙当 t7=‘U’ 时,他从 (3,3) 移动到 (2,3)。
他最终位于单元格 (2,3),行动过程中经过或到达的不同房子的数量为 1。