[USACO21DEC] Walking Home B
题目描述
奶牛 Bessie 正准备从她最喜爱的草地回到她的牛棚。
农场位于一个 $N \times N$ 的方阵上($2 \leq N \leq 50$),其中她的草地在左上角,牛棚在右下角。Bessie 想要尽快回家,所以她只会向下或向右走。有些地方有草堆(haybale),Bessie 无法穿过;她必须绕过它们。
Bessie 今天感到有些疲倦,所以她希望改变她的行走方向至多 $K$ 次($1 \leq K \leq 3$)。
Bessie 有多少条不同的从她最爱的草地回到牛棚的路线?如果一条路线中 Bessie 经过了某个方格而另一条路线中没有,则认为这两条路线不同。
输入输出格式
输入格式
每个测试用例的输入包含 $T$ 个子测试用例,每个子测试用例描述了一个不同的农场,并且必须全部回答正确才能通过整个测试用例。输入的第一行包含 $T$($1 \leq T \leq 50$)。每一个子测试用例如下。
每个子测试用例的第一行包含 $N$ 和 $K$。
以下 $N$ 行每行包含一个长为 $N$ 的字符串。每个字符为 $\texttt{.}$,如果这一格是空的,或 $\texttt{H}$,如果这一格中有草堆。输入保证农场的左上角和右下角没有草堆。
输出格式
输出 $T$ 行,第 $i$ 行包含在第 $i$ 个子测试用例中 Bessie 可以选择的不同的路线数量。
输入输出样例
输入样例 #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 组成的字符串来表示 Bessie 的路线,其中 D 和 R 分别表示 Bessie 向下(down)或向右(right)移动。
第一个子测试用例中,Bessie 的两条可能的路线为 DDRR 和 RRDD。
第二个子测试用例中,Bessie 的四条可能的路线为 DDRR,DRRD,RDDR 和 RRDD。
第三个子测试用例中,Bessie 的六条可能的路线为 DDRR,DRDR,DRRD,RDDR,RDRD 和 RRDD。
第四个子测试用例中,Bessie 的两条可能的路线为 DDRR 和 RRDD。
第五和第六个子测试用例中,Bessie 不可能回到牛棚。
第七个子测试用例中,Bessie 的六条可能的路线为 DDRDRR,DDRRDR,DDRRRD,RRDDDR,RRDDRD 和 RRDRDD。
【数据范围】
- 测试点 2 满足 $K = 1$。
- 测试点 3-5 满足 $K = 2$。
- 测试点 6-10 满足 $K = 3$。