Walking Home

题目描述

奶牛 Bessie 想从她最喜欢的牧场走回她的牛棚。 牧场和农场位于一个 $N \times N$ 的网格上（$2 \leq N \leq 50$），其中牧场在左上角，牛棚在右下角。Bessie 想尽快回家，所以她只会向下和向右走。有些位置有干草堆，Bessie 不能穿过；她必须绕开它们。 Bessie 今天有点累，所以她最多只想改变行走方向 $K$ 次（$1 \leq K \leq 3$）。 从她最喜欢的牧场到牛棚，Bessie 一共有多少条不同的路径？ 如果在一条路径中 Bessie 走过某个格子而在另一条路径中没有走过，则认为这两条路径不同。

输入格式

输入的每个测试用例包含 $T$ 个子测试用例，每个子测试用例描述一个不同的农场，并且必须全部答对才能通过该测试用例。输入第一行包含 $T$（$1 \leq T \leq 50$）。接下来是这 $T$ 个子测试用例。 每个子测试用例首先是一行，包含 $N$ 和 $K$。 接下来的 $N$ 行每行包含一个长度为 $N$ 的字符串。每个字符要么是 $\texttt{.}$ 表示空地，要么是 $\texttt{H}$ 表示有干草堆。保证农场的左上角和右下角不含干草堆。

输出格式

输出 $T$ 行，第 $i$ 行输出第 $i$ 个子测试用例中，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...

2
4
6
2
0
0
6

提示

我们将 Bessie 的可行路径表示为由 D 和 R 组成的字符串，分别表示 Bessie 向下或向右移动。 在第一个子测试用例中，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。 SCORING: 测试点 2 满足 $K = 1$。 测试点 3-5 满足 $K = 2$。 测试点 6-10 满足 $K = 3$。 题目致谢：Nick Wu

来源

USACO 2021 December Contest, Bronze Problem 3（题目致谢：Nick Wu）