컴백홈
면접 대비시간 제한2초메모리 제한128 MB
5x5 이하 격자에서 막힌 칸을 피해 왼쪽 아래에서 오른쪽 위까지 정확히 K개의 칸을 지나는 단순 경로의 수를 구합니다.
문제
한수는 캠프를 마치고 집으로 돌아가려 한다. 시작 위치는 맵의 왼쪽 아래 칸이고, 집은 오른쪽 위 칸이다. 한 번 방문한 칸은 다시 방문하지 않으며, T로 표시된 칸은 지나갈 수 없다.
R x C 격자와 정수 K가 주어질 때, 시작 위치에서 집까지 도착하는 단순 경로 중 경로의 길이가 정확히 K인 경우의 수를 구하라. 여기서 길이는 시작 칸과 도착 칸을 포함하여 방문한 칸의 개수이다.
입력
첫 줄에 정수 R(1 <= R <= 5), C(1 <= C <= 5), K(1 <= K <= R x C)가 공백으로 구분되어 주어진다.
다음 R개의 줄에는 맵 정보가 주어진다. 각 줄은 길이가 C이며, 지나갈 수 있는 칸 .과 지나갈 수 없는 칸 T로만 이루어진다.
출력
거리 K로 집에 도착하는 경우의 수를 출력한다.