P7995 [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 经过了某个方格而另一条路线中没有，则认为这两条路线不同。

无

无

【样例解释】 我们将使用一个由字符 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$。