Bessie the cow is trying to walk from her favorite pasture back to her barn.

The pasture and farm are on an \(N \times N\) grid (\(2 \leq N \leq 50\)), with her
pasture in the top-left corner and the barn in the bottom-right corner. Bessie
wants to get home as soon as possible, so she will only walk down and to the
right. There are haybales in some locations that Bessie cannot walk through; she
must walk around them.

Bessie is feeling a little tired today, so she wants to change the direction she
walks at most \(K\) times (\(1 \leq K \leq 3\)) .

How many distinct paths can Bessie walk from her favorite pasture to the barn?
Two paths are distinct if Bessie walks in a square in one path but not in the
other.

Problem credits: Nick Wu

SCORING

• Test case 2 satisfies \(K = 1\).
• Test cases 3-5 satisfy \(K = 2\).
• Test cases 6-10 satisfy \(K = 3\).

Problem credits: Nick Wu

The input for each test case contains \(T\) sub-test cases, each describing a
different farm and each of which must be answered correctly to pass the full
test case. The first line of input contains \(T\) (\(1 \leq T \leq 50\)). Each of
the \(T\) sub-test cases follow.

Each sub-test case starts with a line containing \(N\) and \(K\).

The next \(N\) lines each contain a string of \(N\) characters. Each character is
either \(\texttt{.}\) if it is empty or \(\texttt{H}\) if it has a haybale. It is
guaranteed the top-left and bottom-right corners of the farm will not contain
haybales.

Output \(T\) lines, the \(i\)th line containing the number of distinct paths Bessie
can take in the \(i\)th sub-test case.

riseoj 작성

출처 올림피아드 > USACO > 2021-2022 > December > Bronze