[고등부] 2024 KOI 1차대회 대비 모의고사 (4주차)

학생들의 모의고사 결과가 마음에 들지 않았던 송준혁 멘토는 마침내 학생들을 가둬 공부 시키기로 했다! (사실이 아닙니다.)

감옥은 N행 M열의 격자 모양이다.

감옥의 각 칸 사이는 막혀있어 이동할 수 없다.

하지만 송준혁 멘토는 여러분이 코딩을 잘하면 탈출할 수 있도록 장치를 만들어 두었다.

감옥의 각 칸 바닥에는 점프대가 있어 상하좌우 중 한 방향으로 최대 K칸까지 점프할 수 있다.

이 점프대를 타고 열심히 움직여 감옥 밖으로 점프 할 수 있다면 여러분의 승리다.

하지만 정작 준혁 멘토는 공부를 똑바로 안해서 감옥을 제대로 만들지 못했다!

애초에 설계가 잘못되어 어떤 칸에서는 아무리 열심히 뛰어도 탈출할 수 없다.

여러분이 이 감옥을 탈출하고 싶다면 탈출 가능한 시작점이 몇 개인지라도 알아두는 편이 좋을 것이다...

준혁 멘토는 계산을 못한다고 하니 여러분이 한 번 계산해보자!

(주의 : 정올의 stack memory가 작은 관계로 너무 깊은 재귀 함수 호출로 인한 런타임 에러가 발생할 수 있습니다. 구현할 때 유의해주세요.)

입력

첫 줄에 N, M, K 가 주어진다.

이후 N행 M열의 문자로 감옥의 정보가 주어진다.

각 문자는 U, D, L, R 중의 하나로 각각 점프대의 위, 아래, 왼쪽, 오른쪽 방향을 의미한다.

출력

한 줄에 탈출 가능한 시작 칸의 개수를 출력하라.

부분문제

번호	점수	조건
#1	25점	N, M \le 500, K \le min(N, M)
#2	75점	N, M \le 2000, K \le min(N, M)

탈출
서브태스크

2.5초 1024MB