레이팅 미적용소 베시는 가장 좋아하는 목초지에서 축사로 걸어서 돌아가려 한다.
목초지와 농장은 \(N \times N\) 격자 (\(2 \leq N \leq 50\)) 위에 있으며, 목초지는 왼쪽 위 모서리에, 축사는 오른쪽 아래 모서리에 있다. 베시는 최대한 빨리 집에 가고 싶으므로 아래쪽과 오른쪽으로만 걷는다. 일부 위치에는 베시가 지나갈 수 없는 건초 더미가 있어서, 이를 돌아가야 한다.
베시는 오늘 조금 피곤해서 걷는 방향을 최대 \(K\) (\(1 \leq K \leq 3\))번만 바꾸고 싶어 한다.
베시가 가장 좋아하는 목초지에서 축사까지 걸어갈 수 있는 서로 다른 경로는 몇 개인가? 한 경로에서는 지나가지만 다른 경로에서는 지나가지 않는 칸이 존재하면 두 경로는 서로 다른 것이다.
출제자: Nick Wu
채점 방식
- 테스트 케이스 2는 \(K = 1\)을 만족한다.
- 테스트 케이스 3-5는 \(K = 2\)를 만족한다.
- 테스트 케이스 6-10은 \(K = 3\)을 만족한다.
출제자: Nick Wu
각 테스트 케이스의 입력은 \(T\)개의 서브 테스트 케이스를 포함하며, 각각은 서로 다른 농장을 나타내고 전체 테스트 케이스를 통과하려면 모두 정확히 답해야 한다. 입력의 첫째 줄에 \(T\) (\(1 \leq T \leq 50\))가 주어진다. 이어서 \(T\)개의 서브 테스트 케이스가 주어진다.
각 서브 테스트 케이스는 \(N\)과 \(K\)가 주어지는 줄로 시작한다.
다음 \(N\)개의 줄에 각각 \(N\)개의 문자로 이루어진 문자열이 주어진다. 각 문자는 빈 칸이면 \(\texttt{.}\), 건초 더미가 있으면 \(\texttt{H}\)이다. 농장의 왼쪽 위와 오른쪽 아래 모서리에는 건초 더미가 없음이 보장된다.
\(T\)개의 줄을 출력한다. \(i\)번째 줄에는 \(i\)번째 서브 테스트 케이스에서 베시가 택할 수 있는 서로 다른 경로의 수를 출력한다.
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
6We'll denote Bessie's possible paths as strings of D's and R's, indicating that
Bessie moved either down or right, respectively.
In the first sub-test case, Bessie's two possible walks are DDRR and RRDD.
In the second sub-test case, Bessie's four possible walks are DDRR, DRRD, RDDR,
and RRDD.
In the third sub-test case, Bessie's six possible walks are DDRR, DRDR, DRRD,
RDDR, RDRD, and RRDD.
In the fourth sub-test case, Bessie's two possible walks are DDRR and RRDD.
In the fifth and sixth sub-test cases, it is impossible for Bessie to walk back
to the barn.
In the seventh sub-test case, Bessie's six possible walks are DDRDRR, DDRRDR,
DDRRRD, RRDDDR, RRDDRD, and RRDRDD.
riseoj 작성
출처 올림피아드 > USACO > 2021-2022 > December > Bronze