走路回家

题目描述

奶牛 Bessie 正准备从她最喜爱的草地回到她的牛棚。农场位于一个 $N \times N$ 的方阵上，其中她的草地在左上角，牛棚在右下角。Bessie 只会向下或向右走。有些地方有草堆（H），Bessie 无法穿过。Bessie 希望改变她的行走方向至多 $K$ 次。Bessie 有多少条不同的从草地回到牛棚的路线？

输入格式

输入的第一行包含 $T$。每个子测试用例的第一行包含 $N$ 和 $K$。以下 $N$ 行每行包含一个长为 $N$ 的字符串。

输出格式

输出 $T$ 行，每行包含路线数量。

样例输入 #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

数据范围

$1 \le T \le 50, 2 \le N \le 50, 1 \le K \le 3$

知识点与难度

本题涉及的知识点从隶属于 GESP六级（记忆化搜索、DFS），难度等级：⭐⭐⭐⭐⭐。

测试点分布