C++ 动态规划解决方格图路径问题：转弯次数限制

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

首先，定义一个二维数组 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 次。