C++ 实现 N*N 方格图路径计数：带障碍物和转弯限制

{}下面是使用C++实现的代码：

{}```cpp #include <iostream> #include <vector> #include <cstring> using namespace std;

const int MAXN = 50; const int MAXM = 50;

int dp[MAXN+1][MAXN+1][MAXM+1]; char grid[MAXN+1][MAXN+1]; int n, m;

int solve(int x, int y, int k) { if (x > n || y > n || grid[x][y] == 'h') return 0; if (x == n && y == n) return 1; if (dp[x][y][k] != -1) return dp[x][y][k];

int ans = 0;
if (k > 0) {
    ans = solve(x+1, y, k-1) + solve(x, y+1, k-1);
} else {
    ans = solve(x+1, y, k) + solve(x, y+1, k);
}

dp[x][y][k] = ans;
return ans;

}

int main() { int t; cin >> t;

while (t--) {
    cin >> n >> m;
    
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> grid[i][j];
        }
    }
    
    memset(dp, -1, sizeof(dp));
    
    int ans = solve(1, 1, m);
    cout << ans << endl;
}

return 0;

}

代码中，`dp[i][j][k]`表示从起点到坐标`(i, j)`并且转弯次数不超过`k`的路径总数。初始时，所有的`dp`值都设为-1。`solve`函数根据题目要求递归计算路径总数。如果当前坐标`(x, y)`超出边界或者是障碍物，则返回0。如果当前坐标是终点，则返回1。如果`dp[x][y][k]`已经计算过，则直接返回其结果。否则，根据转弯次数是否大于0，分别计算向下和向右的路径总数，并将结果存入`dp[x][y][k]`中。最后在主函数中读取输入数据，调用`solve`函数进行计算，并输出结果。

注意，由于`n`的范围较大，使用递归方法可能会导致栈溢出。可以考虑使用动态规划的方法来解决此问题。