#USACOC2214C. Walking Home

Walking Home

Description

奶牛 Bessie 正准备从她最喜爱的草地回到她的牛棚。

农场位于一个 N×NN \times N 的方阵上,其中她的草地在左上角,牛棚在右下角。Bessie 想要尽快回家,所以她只会向下或向右走。有些地方有草堆(haybale),Bessie 无法穿过;她必须绕过它们。

Bessie 今天感到有些疲倦,所以她希望改变她的行走方向至多 KK 次。

Bessie 有多少条不同的从她最爱的草地回到牛棚的路线?如果一条路线中 Bessie 经过了某个方格而另一条路线中没有,则认为这两条路线不同。

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

Input Format

每个测试用例的输入包含 TT 个子测试用例,每个子测试用例描述了一个不同的农场,并且必须全部回答正确才能通过整个测试用例。输入的第一行包含 TT。每一个子测试用例如下。

每个子测试用例的第一行包含 NNKK

以下 NN 行每行包含一个长为 NN 的字符串。每个字符为 .\texttt{.},如果这一格是空的,或 H\texttt{H},如果这一格中有草堆。输入保证农场的左上角和右下角没有草堆。

  • 1T501 \leq T \leq 50

Output Format

输出 TT 行,第 ii 行包含在第 ii 个子测试用例中 Bessie 可以选择的不同的路线数量。

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

  • 测试点 2 满足 K=1K = 1
  • 测试点 3-5 满足 K=2K = 2
  • 测试点 6-10 满足 K=3K = 3

Problem Credit

供题:Nick Wu