题目背景

原题为 P7995 [USACO21DEC] Walking Home B

题目描述

Gooby 正准备回家。

我们可以把地图看作一个 $N \times N$ 的方阵（$2 \leq N \leq 50$），其中 Gooby 位于左上角，他的家在右下角。Gooby 希望尽快回家，所以他只会向下或向右走。有些地方有障碍物，Gooby 无法穿过，他必须绕过它们。

Gooby 今天感到有些疲倦，所以他希望改变他的行走方向至多 $K$ 次（$1 \leq K \leq 3$）。

Gooby 有多少条不同的回到家的路线？如果一条路线中 Gooby 经过了某个方格而另一条路线中没有，则认为这两条路线不同。

输入格式

每个测试用例的输入包含 $T$ 个测试用例（$1 \leq T \leq 50$）。

每个子测试用例的第一行包含 $N$ 和 $K$。

以下 $N$ 行每行包含一个长为 $N$ 的字符串。每个字符为 $\texttt{.}$，表示这一格是空的；或 $\texttt{H}$，表示这一格中有障碍物。输入保证地图的左上角和右下角没有障碍物。

输出格式

输出 $T$ 行，第 $i$ 行包含在第 $i$ 个子测试用例中 Gooby 可以选择的不同的路线数量。

输入输出样例 #1

输入 #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...

输出 #1

2
4
6
2
0
0
6

说明/提示

【样例解释】

我们将使用一个由字符 D 和 R 组成的字符串来表示 Gooby 的路线，其中 D 和 R 分别表示 Gooby 向下（down）或向右（right）移动。

第一个测试用例中，Gooby 的两条可能的路线为 DDRR 和 RRDD。

第二个测试用例中，Gooby 的四条可能的路线为 DDRR，DRRD，RDDR 和 RRDD。

第三个测试用例中，Gooby 的六条可能的路线为 DDRR，DRDR，DRRD，RDDR，RDRD 和 RRDD。

第四个测试用例中，Gooby 的两条可能的路线为 DDRR 和 RRDD。

第五和第六个测试用例中，Gooby 不可能回到家。

第七个测试用例中，Gooby 的六条可能的路线为 DDRDRR，DDRRDR，DDRRRD，RRDDDR，RRDDRD 和 RRDRDD。

【数据范围】

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