有一个NN的棋盘形式方格矩阵，小明在矩阵的左上角(1,1)位置，现在他要走到右下角(N,N)位置，他只能向下或向右走。有的方格上有障碍物，小明就不能到达有障碍物的格子，必须绕着走，但是至多只有K次机会来改变自己行走的方向。那么小明有多少种方案可以到达右下角位置。 输入 输入包含多组测试数据。 输入第1行一个整数T，表示多组测试数据。 对于每组测试数据，第1行先输入2个整数N和K； 接下来输入一个NN的字符矩阵，其中“.”表示这个方格没有障碍物，“H”表示这个方格有障碍物。 输入数据保证左上角和右下角是没有障碍物的。 输出 输出一共T行，每行一个整数，表示小明可选的方案数。 输入样例1

3 3 1 ... ... ... 3 2 ... ... ... 3 3 ... ... ... 输出样例 2 4 6

这道题咋做 在线等 dfs我炸了