C++ 算法：有限转弯次数的方格图路径计数问题

题目要求计算从左上角到右下角的路径数量，每次只能向下或向右走，碰到障碍必须绕过，且转弯次数不能超过 m 次。

思路：

1. 创建一个二维数组 dp，dp[i][j]表示从起点到达(i, j)位置的路径数量。
2. 初始化 dp[0][0]为1，表示起点到起点的路径数量为1。
3. 遍历每个位置(i, j)：
   • 如果当前位置为障碍('h')，则将 dp[i][j]设为0。
   • 否则，将 dp[i][j]设为 dp[i-1][j] + dp[i][j-1]，表示从上方和左方到达该位置的路径数量之和。
4. 遍历完成后，dp[n-1][n-1]即为从起点到终点的路径数量。

为了限制转弯次数不超过 m 次，可以在计算 dp[i][j]时，判断上方和左方位置的转弯次数是否已经达到了 m 次，如果达到了则不考虑该方向的路径数量。

代码如下：

#include <iostream>
#include <cstring>
using namespace std;

const int MAX_N = 50;

int main() {
    int T;
    cin >> T;  // 输入测试组数
    while (T--) {
        int n, m;
        char grid[MAX_N][MAX_N];
        cin >> n >> m;  // 输入方格图的大小和最大转弯次数

        // 输入方格图
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                cin >> grid[i][j];
            }
        }

        int dp[MAX_N][MAX_N];
        memset(dp, 0, sizeof(dp));

        dp[0][0] = 1;  // 起点到起点的路径数量为1

        // 计算路径数量
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 'h') {
                    dp[i][j] = 0;  // 障碍，路径数量为0
                } else {
                    if (i > 0 && dp[i-1][j] > 0) {
                        // 上方位置的路径数量不为0，且转弯次数未达到m次
                        dp[i][j] += dp[i-1][j];
                    }
                    if (j > 0 && dp[i][j-1] > 0) {
                        // 左方位置的路径数量不为0，且转弯次数未达到m次
                        dp[i][j] += dp[i][j-1];
                    }
                }
            }
        }

        cout << dp[n-1][n-1] << endl;
    }

    return 0;
}

上述代码使用动态规划的思想，时间复杂度为O(n^2)。