문제
준우는 자신이 학원에서 집으로 돌아갈 준비를 하고 있습니다.
N×N 정방형 행렬(2≤N≤50)에서 학원은 왼쪽 상단 모서리에 있고 집은 오른쪽 하단 모서리에 있습니다.
준우는 가능한 한 빨리 집에 가고 싶어하므로 아래로 또는 오른쪽으로만 갈 것입니다.
일부 장소에는 불량배들이 있어 준우가 통과할 수 없습니다.
준우는 오늘 약간 피곤해서 걷는 방향을 최대 K번(1≤K≤3)까지만 변경하려고 합니다.
준우는 학원에서 집까지 얼마나 많은 다른 경로를 통해 갈 수 있는지 계산하는 프로그램을 작성합시다.
입력
첫 번째 줄에는 T(1≤T≤50)가 주어진다.
각 하위 테스트 케이스의 첫 번째 줄에는 N과 K가 주어진다.
다음 N 줄은 각각 길이가 N인 문자열이 주어진다. 각 문자는 셀이 비어 있으면 .이고 셀에 불량배가 있으면 H이다.
학원과 집의 위치인 좌측 상단과 우측 하단은 .으로 표시한다.
출력
준우가 i번째 하위 테스트 케이스에서 선택 가능한 경로의 수를 i번째 라인에 출력하시오.
예제1
입력
7
3 1
...
...
...
3 2
...
...
...
3 3
...
...
...
3 3
...
.H.
...
3 2
.HH
HHH
HH.
3 3
.H.
H..
...
4 3
...H
.H..
....
H...
출력
2
4
6
2
0
0
6
힌트
출처
USACO 2021 December Bronze