n*n 方格图路径计数：限制转弯次数的动态规划解法

这是一个典型的动态规划问题。可以定义一个二维数组 dp[n][n][m]，其中 dp[i][j][k] 表示从起点(1,1)到达位置(i,j)，且转弯次数不超过 k 的路径数。

根据题意，可以得到以下状态转移方程：

1. 如果位置(i,j)是障碍物，则 dp[i][j][k] = 0。
2. 如果位置(i,j)不是障碍物，则 dp[i][j][k] = dp[i-1][j][k] + dp[i][j-1][k]。即可以从上方或左方到达当前位置。
3. 如果位置(i,j)不是障碍物且 k > 0，则 dp[i][j][k] += dp[i-1][j][k-1] + dp[i][j-1][k-1]。即可以从上方或左方到达当前位置，并且转弯次数减少1次。

根据以上状态转移方程，可以使用动态规划求解问题。具体代码如下（使用Python实现）：

def solve(n, m, grid):
    dp = [[[0] * (m+1) for _ in range(n)] for _ in range(n)]
    dp[0][0][0] = 1

    for i in range(n):
        for j in range(n):
            if grid[i][j] == 'h':
                continue

            for k in range(m+1):
                if i > 0:
                    dp[i][j][k] += dp[i-1][j][k]
                    if k > 0:
                        dp[i][j][k] += dp[i-1][j][k-1]

                if j > 0:
                    dp[i][j][k] += dp[i][j-1][k]
                    if k > 0:
                        dp[i][j][k] += dp[i][j-1][k-1]

    return dp[n-1][n-1][m]

对于每组数据，可以先读取 n 和 m，然后读取 n 行输入作为方格图的表示。然后调用 solve 函数即可得到结果。

t = int(input())
for _ in range(t):
    n, m = map(int, input().split())
    grid = [input() for _ in range(n)]
    ans = solve(n, m, grid)
    print(ans)

上述代码的时间复杂度为 O(n^3 * m)，适用于给定的数据范围。