시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 (추가 시간 없음) | 1024 MB (추가 메모리 없음) | 535 | 235 | 171 | 40.618% |
한별이는 출근하던 도중 이세계 대환장 버스에 치였다.
그림 B.1: 이세계 대환장 버스
그림 B.2: 출근하는 한별이
올해 휴가를 전부 써 버려 당장 판교로 돌아가야 하는 한별이는 돌아가기 위한 방법을 어떻게든 찾아보기 위해 이세계를 돌아다녀 보려고 한다.
이세계는 $R\times C$의 격자로 되어 있다. 지금은 밤이어서 한별이는 자신이 위치한 칸 및 그 칸에서 위, 아래, 왼쪽 또는 오른쪽으로 인접한 칸만을 볼 수 있지만, 와드를 설치하면 조금 더 넓은 영역의 시야를 확보할 수 있다. 구체적으로는, 격자의 모든 칸은 각각 어떤 영역 하나에 속해 있는데, 와드를 놓으면 와드가 놓인 칸이 속한 영역에 있는 모든 칸을 볼 수 있게 된다.
한별이의 여행 기록이 주어질 때 한별이가 얼마나 넓은 시야를 확보했을지 계산해 보자.
첫 번째 줄에는 격자의 크기를 나타내는 두 정수 $R$과 $C$가 주어진다. ($1 \le R,C \le 1\,000$)
다음 줄부터 $R$개의 줄에 걸쳐 격자의 정보가 주어진다. 각 줄은 $C$개의 알파벳 소문자로 이루어져 있으며, 위, 아래, 왼쪽 또는 오른쪽으로 인접해 있는 칸이 같은 문자라는 것은 두 칸이 같은 영역에 속해 있음을 의미한다.
다음 줄에는 한별이가 이세계에 떨어진 위치를 나타내는 두 정수 $H_R$, $H_C$가 주어진다. 이는 한별이가 위에서 $H_R$번째 줄, 왼쪽에서 $H_C$번째 칸에 떨어졌음을 의미한다. ($1 \le H_R \le R$, $1 \le H_C \le C$)
마지막 줄에는 한별이의 여행 기록을 나타내는 $200\,000$글자 이하의 문자열이 주어진다. 여행 기록의 각 문자는 U
, D
, L
, R
, W
중 하나로 이루어져 있으며, U
, D
, L
, R
은 각각 위, 아래, 왼쪽, 오른쪽으로 한 칸 이동했다는 뜻이고, W
는 지금 있는 칸에 와드를 설치했다는 뜻이다. 한별이가 격자를 벗어나는 경우는 주어지지 않는다.
$R$개의 줄에 걸쳐 한별이의 시야를 출력한다. 각 줄은 $C$개의 문자로 되어 있어야 하며, $R$번째 줄 $C$번째 문자가 .
이라면 한별이의 시야에 해당 칸이 들어와 있다는 뜻이고 #
이라면 그렇지 않다는 뜻이다.
4 5 aaabc dcbbc dccaa ddaaa 3 4 WLLLWUURRD
##.## ....# .#... .....
3 3 abc def ghi 2 2 LU
..# .## ###
와드를 설치하지는 않았지만, 한별이의 최종 위치의 위, 아래, 왼쪽, 오른쪽 칸은 시야로 확보하고 있다.
지나온 경로를 모두 시야로 확보하지는 않는다.
University > 서강대학교 > 2021 Sogang Programming Contest > Champion B번
University > 서강대학교 > 2021 Sogang Programming Contest > Open J번