给出个nn的方格图其中代表空地h代表障碍。从图的左上角11走到右下角nn每次只能向下或向右走碰到障碍必须绕过且转弯次数不能超过 m 次请问有多少种方法？注意n=50且有最多50组数据。请使用C++并尽量不要使用vector

题目可以使用动态规划来解决。

首先，定义一个二维数组dp[n][n]，其中dp[i][j]表示从起点(1,1)到达点(i,j)的路径数量。

然后，我们可以根据动态规划的思路进行状态转移。对于每个点(i,j)，它可以从上方的点(i-1,j)或者左方的点(i,j-1)到达。如果点(i,j)上有障碍物，那么dp[i][j]的值应该为0，否则dp[i][j]的值等于dp[i-1][j]和dp[i][j-1]的和。

但是，题目要求转弯次数不能超过m次。所以我们需要增加一个维度k，表示当前路径已经转弯的次数。定义一个三维数组dp[n][n][m+1]，其中dp[i][j][k]表示从起点(1,1)到达点(i,j)，并且已经转弯了k次的路径数量。

接下来，我们可以根据转弯的次数k进行状态转移。对于每个点(i,j)，它可以从上方的点(i-1,j)或者左方的点(i,j-1)到达。如果点(i,j)上有障碍物，那么dp[i][j][k]的值应该为0，否则dp[i][j][k]的值等于dp[i-1][j][k]和dp[i][j-1][k]的和。

但是，如果点(i,j)上没有障碍物，并且已经转弯了k次，那么它还可以从上方的点(i-1,j)或者左方的点(i,j-1)转弯到达。所以，dp[i][j][k]的值还需要加上dp[i-1][j][k-1]和dp[i][j-1][k-1]的和。

最后，答案就是dp[n][n][m]。

下面是C++的代码实现：

#include <iostream>
#include <cstring>

using namespace std;

const int MAX_N = 50;

int main() {
    int T;
    cin >> T; // 输入数据组数
    while(T--) {
        int n, m;
        cin >> n >> m; // 输入方格图的大小和转弯次数
        char grid[MAX_N][MAX_N];
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                cin >> grid[i][j]; // 输入方格图
            }
        }
        
        // 初始化dp数组
        int dp[MAX_N][MAX_N][MAX_N];
        memset(dp, 0, sizeof(dp));
        
        // 初始化起点
        dp[0][0][0] = 1;
        
        // 动态规划求解
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                for(int k = 0; k <= m; k++) {
                    if(grid[i][j] == 'h') {
                        dp[i][j][k] = 0;
                    } else {
                        dp[i][j][k] += (i > 0 ? dp[i-1][j][k] : 0) + (j > 0 ? dp[i][j-1][k] : 0);
                        if(k > 0) {
                            dp[i][j][k] += (i > 0 ? dp[i-1][j][k-1] : 0) + (j > 0 ? dp[i][j-1][k-1] : 0);
                        }
                    }
                }
            }
        }
        
        // 输出结果
        cout << dp[n-1][n-1][m] << endl;
    }
    
    return 0;
}

这样，我们就可以通过动态规划求解给定方格图的路径数量，并且转弯次数不超过m次。