#USACOC2214C. Walking Home

Walking Home

Description

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, with herpasture in the top-left corner and the barn in the bottom-right corner. Bessiewants to get home as soon as possible, so she will only walk down and to theright. There are haybales in some locations that Bessie cannot walk through; shemust walk around them.

Bessie is feeling a little tired today, so she wants to change the direction shewalks at most KK times .

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 theother.

  • 2N502 \leq N \leq 50
  • 1K31 \leq K \leq 3

Input Format

The input for each test case contains TT sub-test cases, each describing adifferent farm and each of which must be answered correctly to pass the fulltest case. The first line of input contains TT. Each ofthe 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 iseither .\texttt{.} if it is empty or H\texttt{H} if it has a haybale. It isguaranteed the top-left and bottom-right corners of the farm will not containhaybales.

  • 1T501 \leq T \leq 50

Output Format

Output TT lines, the ii-th line containing the number of distinct paths Bessiecan take in the ii-th sub-test case.

7
3 1
...
...
...
3 2
...
...
...
3 3
...
...
...
3 3
...
.H.
...
3 2
.HH
HHH
HH.
3 3
.H.
H..
...
4 3
...H
.H..
....
H...
7
3 1
...
...
...
3 2
...
...
...
3 3
...
...
...
3 3
...
.H.
...
3 2
.HH
HHH
HH.
3 3
.H.
H..
...
4 3
...H
.H..
....
H...

Scoring

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

Problem Credit

Problem credits: Nick Wu