查找在C ++中达到矩阵末尾所需的最少步骤

  • Z时代
  • 2024-01-10
  • 分类：综合

假设我们有一个带有正整数的2D矩阵。我们必须找到从矩阵的末尾（最底部的单元格）移动所需的最小步骤。如果我们在单元格(i,j)，则可以转到单元格（i，j + mat [i，j ]）或（i + mat [i，j]，j），我们无法越界。所以如果矩阵像-

212
111
111

输出为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

以上是 查找在C ++中达到矩阵末尾所需的最少步骤 的全部内容， 来源链接： utcz.com/z/327067.html

回到顶部