#PU1157. USACO 2021 December Contest, Bronze — Problem 3. Walking Home

USACO 2021 December Contest, Bronze — Problem 3. Walking Home

USACO 2021 December Contest, Bronze — Problem 3. Walking Home

题目描述

Bessie the cow is trying to walk from her favorite pasture back to her barn. The pasture and farm are on an N×NN \times N grid (2≤N≤502 \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 KK times (1≤K≤31 \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.

输入格式

The input for each test case contains TT 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 TT (1≤T≤501 \leq T \leq 50). Each of the TT sub-test cases follow. Each sub-test case starts with a line containing NN and KK. The next NN lines each contain a string of NN characters. Each character is either .\texttt{.} if it is empty or H\texttt{H} if it has a haybale. It is guaranteed the top-left and bottom-right corners of the farm will not contain haybales.

输出格式

(见题面原文)

数据范围

Test case 2 satisfies K=1K = 1. Test cases 3-5 satisfy K=2K = 2. Test cases 6-10 satisfy K=3K = 3. Problem credits: Nick Wu

样例

样例 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
We'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.