1：题意

给定一个 $N \times N$ 的区域，区域中的每个点由 0 或 1 组成，1 类点不能走 0 类点可以走。问你从左上角走到右下角，并且最多转向 $K$ 次有多少种走法。

2：分析

看到在格子图中问有多少走法的题目，可以比较容易的想到使用 dp 算法解决，具体做法参考 P1002过河卒，但是本题的难点以及本题解的重点在于如何处理对于转向次数的限制。

根据上图，我们可以看到，路径是否包含转向不仅跟从哪个点转移来有关，还和转移来的那个点是从哪个点转移来的有关（从左边或是从右边）。具体的判断规则如下，可以对照着图来理解：

如果当前点是从上面的点 map[i - 1][j] 转移来的，并且上面那个点是从他的左边转移来的，那么会发生一次转移。（图中当前点上方的蓝色虚线）
如果当前点是从左边的点 map[i][j - 1] 转移来的，并且左边那个点是从他的上方转移来的，那么会发生一次转移。（图中当前点左方的蓝色虚线）
其他所有情况不会发生转向

我们让 dp[i][j][k][t] 表示走到 $(i,j)$ ，花费了 $k$ 次转向，并且是从左边 (0) ，或是上面 (1) 的格子转移来的。

有了以上的判断规则，我们可以写出 dp 的转移方程。

发生转向的情况:

dp[i][j][k][0] += dp[i][j - 1][k - 1][1];
dp[i][j][k][1] += dp[i - 1][j][k - 1][0];

不发生转向的情况：

dp[i][j][k][0] += dp[i][j - 1][k][0];
dp[i][j][k][1] += dp[i - 1][j][k][1];

其中，我们需要注意如果一个点如果是从 $(1,1)$ ，也就是起点转移过来的话，是不可能发生转向的。并且如果循环中的 $k=0$ 的话也是不可能发生转向的（ $k$ 代表转向次数）。所以我们还需要在发生转向时的状态转移方程加入如下的判断语句：

if (k != 0 && i != 1 && j != 1)

最后，还需要注意一点。因为题目问的是“至多转向 $k$ 次”，所以最后输出时需要把所有符合条件的情况加起来再一起输出。

3：程序实现

完整代码及注释如下：

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 55;
int n, k;
int t, mp[MAXN][MAXN];
int dp[MAXN][MAXN][4][2]; //dp[i j k t]是到i，j，转了k次的方法数量，并且上次是从左/上边的格子转移来的

void calc_dp()
{
    memset(dp, 0, sizeof(dp));
    dp[1][1][0][0] = dp[1][1][0][1] = 1;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            if (mp[i][j])
                for (int k = 0; k <= 3; k++)
                {
                    dp[i][j][k][0] += dp[i][j - 1][k][0];
                    dp[i][j][k][1] += dp[i - 1][j][k][1];
                    if (k != 0 && i != 1 && j != 1)
                    {
                        dp[i][j][k][0] += dp[i][j - 1][k - 1][1];
                        dp[i][j][k][1] += dp[i - 1][j][k - 1][0];
                    }
                }
        }
    }
}
void input()
{
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++)
    {
        char temp[MAXN];
        scanf("%s", temp + 1);
        for (int j = 1; temp[j]; j++)
        {
            if (temp[j] == 'H')
                mp[i][j] = 0;
            else
                mp[i][j] = 1;
        }
    }
}

int main()
{
    scanf("%d", &t);
    while (t--)
    {
        input();
        calc_dp();
        if (k == 3)
            printf("%d\n", dp[n][n][0][0] + dp[n][n][0][1] + dp[n][n][1][0] + dp[n][n][1][1] +
                             dp[n][n][2][0] + dp[n][n][2][1] + dp[n][n][3][0] + dp[n][n][3][1]);
        if (k == 2)
            printf("%d\n", dp[n][n][0][0] + dp[n][n][0][1] + dp[n][n][1][0] + dp[n][n][1][1] +
                             dp[n][n][2][0] + dp[n][n][2][1]);
        if (k == 1)
            printf("%d\n", dp[n][n][0][0] + dp[n][n][0][1] + dp[n][n][1][0] + dp[n][n][1][1]);
    }
    system("pause");
}