查找在C ++中达到矩阵末尾所需的最少步骤
假设我们有一个带有正整数的2D矩阵。我们必须找到从矩阵的末尾（最底部的单元格）移动所需的最小步骤。如果我们在单元格(i,j)，则可以转到单元格（i，j+mat[i，j]）或（i+mat[i，j]，j），我们无法越界。所以如果矩阵像-
输出为2。路径为(0,0)→(0,2)→(2,2)
在这里，我们将使用动态编程方法来解决此问题。假设我们位于像元(i,j)，我们想到达(n-1,n-1)个像元。我们可以使用如下的递归关系-
DP[i，j]=1+min（DP[i+arr[i，j]，j]，DP[i，j+arr[i，j]]）
示例
#include<iostream>
#define N 3
using namespace std;
int table[N][N];
bool temp_val[N][N];
int countSteps(int i, int j, int arr[][N]) {
if (i == N - 1 and j == N - 1)
return 0;
if (i > N - 1 || j > N - 1)
return INT_MAX;
if (temp_val[i][j])
return table[i][j];
temp_val[i][j] = true;
table[i][j] = 1 + min(countSteps(i + arr[i][j], j, arr), countSteps(i, j + arr[i][j], arr));
return table[i][j];
}
int main() {
int arr[N][N] = { { 2, 1, 2 }, { 1, 1, 1 }, { 1, 1, 1 } };
int ans = countSteps(0, 0, arr);
if (ans >= INT_MAX)
cout << -1;
else
cout <<"Number of steps: "<< ans;
}输出结果
Number of steps: 2