| 问题描述 |
|---|
在一张$$n \times n$$的地图中，你从左上角出发，规定每次只能向右或向下走一格，终点是右下角。 求转向次数不超过$$k$$的走法数量。（初始方向可以向右或向下，不计入转向次数） |
| 输入描述 |
第一行是一个正整数$$T$$表示测试案例的数量。（$$1 \leq T \leq 100$$） 每组案例先是正整数$$n$$和$$k$$分别表示地图的大小和最多转向的次数。（$$2 \leq n \leq 50, 1 \leq k \leq 3$$） 接下来$$n \times n$$个字符，这些字符只可能是 保证起点和终点都是 |
| 输出描述 |
针对每组案例，在一行中输出从左上角走到右下角且转向次数不超过$$k$$的方案数。 |
| 样例输入复制样例 |
7 3 1 ... ... ... 3 2 ... ... ... 3 3 ... ... ... 3 3 ... .#. ... 3 2 .## ### ##. 3 3 .#. #.. ... 4 3 ...# .#.. .... #... |
| 样例输出 |
2 4 6 2 0 0 6 |
| 提示说明 |
在第一组案例中，转向次数不超过$$1$$的走法只有： 向右走到头，转向下，走到终点； 向下走到头，转向右，走到终点； 这两种。 |
| 相关 |