C++ 动态规划解决带转弯限制的方格图路径问题

这道题可以使用动态规划来解决。我们可以定义一个二维数组 "dp"，其中 "dp[i][j]" 表示从起点 (1,1) 走到位置 (i,j) 的路径数目。\n\n首先初始化 "dp" 数组，将起点 (1,1) 的路径数目设为 1，其他位置都设为 0。\n\n然后，我们可以从左上角开始依次计算每个位置的路径数目。对于位置 (i,j)，如果该位置是空地，则路径数目等于上方位置 (i-1,j) 和左方位置 (i,j-1) 的路径数目之和。如果该位置是障碍，则路径数目为 0。\n\n但是，我们还需要考虑转弯次数不能超过 m 的限制。我们可以使用一个额外的二维数组 "turns" 来记录每个位置的转弯次数。对于位置 (i,j)，如果该位置是空地，则转弯次数等于上方位置 (i-1,j) 和左方位置 (i,j-1) 的转弯次数之和。如果该位置是障碍，则转弯次数为 0。\n\n在计算路径数目和转弯次数时，我们需要根据上方位置和左方位置是否是障碍来判断是否需要增加转弯次数。如果上方位置是障碍，则转弯次数需要加 1；如果左方位置是障碍，则转弯次数需要加 1。\n\n最后，我们可以返回 "dp" 数组的最后一个元素 "dp[n][n]" 作为结果，即从起点到终点的路径数目。\n\n以下是 C++ 的代码实现：\n\ncpp\n#include <iostream>\n#include <vector>\n\nusing namespace std;\n\nint main() {\n int T;\n cin >> T;\n \n while (T--) {\n int n, m;\n cin >> n >> m;\n \n vector<vector<char>> grid(n, vector<char>(n));\n for (int i = 0; i < n; i++) {\n for (int j = 0; j < n; j++) {\n cin >> grid[i][j];\n }\n }\n \n vector<vector<long long>> dp(n, vector<long long>(n, 0));\n vector<vector<int>> turns(n, vector<int>(n, 0));\n dp[0][0] = 1;\n \n for (int i = 0; i < n; i++) {\n for (int j = 0; j < n; j++) {\n if (grid[i][j] == 'h') {\n continue; // skip obstacles\n }\n \n if (i > 0) {\n dp[i][j] += dp[i-1][j];\n turns[i][j] += turns[i-1][j];\n \n if (grid[i-1][j] == 'h') {\n turns[i][j]++;\n }\n }\n \n if (j > 0) {\n dp[i][j] += dp[i][j-1];\n turns[i][j] += turns[i][j-1];\n \n if (grid[i][j-1] == 'h') {\n turns[i][j]++;\n }\n }\n \n if (turns[i][j] > m) {\n dp[i][j] = 0; // exceed turn limit\n }\n }\n }\n \n cout << dp[n-1][n-1] << endl;\n }\n \n return 0;\n}\n\n\n该算法的时间复杂度为 O(n^2)，空间复杂度为 O(n^2)。