The content below was generated entirely by machine translation. Please verify its accuracy. If anything is unclear, consult the Chinese source version.

1: Problem Statement

Given an $N \times N$ area, each point in the area consists of either 0 or 1. Points of type 1 cannot be traversed, while points of type 0 can be traversed. Find the number of ways to travel from the upper-left corner to the lower-right corner while turning at most $K$ times.

2: Analysis

When we see a problem asking how many paths there are in a grid, it is relatively easy to think of using a DP algorithm. For a specific method, refer to P1002 Crossing the River. However, the difficulty of this problem, and the focus of this solution, is how to handle the limit on the number of turns.

From the figure above, we can see that whether a path contains a turn depends not only on which point it transitions from, but also on which point that previous point transitioned from (from the left or from above). The specific rules are as follows; you can compare them with the figure to understand them:

If the current point is reached from the point above, map[i - 1][j], and that point above was reached from its left, then one turn occurs. (The blue dashed line above the current point in the figure.)
If the current point is reached from the point to the left, map[i][j - 1], and that point to the left was reached from above it, then one turn occurs. (The blue dashed line to the left of the current point in the figure.)
No turn occurs in all other cases.

Let dp[i][j][k][t] represent the number of ways to reach $(i,j)$ using $k$ turns, where the transition came from the cell to the left (0) or the cell above (1).

With the rules above, we can write the DP transition equations.

Cases in which a turn occurs:

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

Cases in which no turn occurs:

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

Here, we need to note that if a point is reached from $(1,1)$ , which is the starting point, then a turn cannot possibly occur. Also, if $k=0$ in the loop, then a turn cannot possibly occur either ( $k$ represents the number of turns). Therefore, we also need to add the following conditional statement to the state-transition equation for cases in which a turn occurs:

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

Finally, one more point needs attention. Because the problem asks for “at most $k$ turns,” all cases that satisfy the condition need to be added together before the final output.

3: Program Implementation

The complete code and comments are as follows:

#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] is the number of ways to reach i, j after turning k times, with the previous transition coming from the cell to the left/above.

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");
}