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

这道题可以使用动态规划来解决。我们可以定义一个二维数组dp，其中dp[i][j]表示从起点(1,1)走到位置(i,j)的路径数目。 首先初始化dp数组，将起点(1,1)的路径数目设为1，其他位置都设为0。 然后，我们可以从左上角开始依次计算每个位置的路径数目。对于位置(i,j)，如果该位置是空地，则路径数目等于上方位置(i-1,j)和左方位置(i,j-1)的路径数目之和。如果该位置是障碍，则路径数目为0。 但是，我们还需要考虑转弯次数不能超过m的限制。我们可以使用一个额外的二维数组turns来记录每个位置的转弯次数。对于位置(i,j)，如果该位置是空地，则转弯次数等于上方位置(i-1,j)和左方位置(i,j-1)的转弯次数之和。如果该位置是障碍，则转弯次数为0。 在计算路径数目和转弯次数时，我们需要根据上方位置和左方位置是否是障碍来判断是否需要增加转弯次数。如果上方位置是障碍，则转弯次数需要加1；如果左方位置是障碍，则转弯次数需要加1。 最后，我们可以返回dp数组的最后一个元素dp[n][n]作为结果，即从起点到终点的路径数目。

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

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int T;
    cin >> T;
    
    while (T--) {
        int n, m;
        cin >> n >> m;
        
        vector<vector<char>> grid(n, vector<char>(n));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                cin >> grid[i][j];
            }
        }
        
        vector<vector<long long>> dp(n, vector<long long>(n, 0));
        vector<vector<int>> turns(n, vector<int>(n, 0));
        dp[0][0] = 1;
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 'h') {
                    continue;  // skip obstacles
                }
                
                if (i > 0) {
                    dp[i][j] += dp[i-1][j];
                    turns[i][j] += turns[i-1][j];
                    
                    if (grid[i-1][j] == 'h') {
                        turns[i][j]++;
                    }
                }
                
                if (j > 0) {
                    dp[i][j] += dp[i][j-1];
                    turns[i][j] += turns[i][j-1];
                    
                    if (grid[i][j-1] == 'h') {
                        turns[i][j]++;
                    }
                }
                
                if (turns[i][j] > m) {
                    dp[i][j] = 0;  // exceed turn limit
                }
            }
        }
        
        cout << dp[n-1][n-1] << endl;
    }
    
    return 0;
}

该算法的时间复杂度为O(n^2)，空间复杂度为O(n^2)。