数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法学研究在C++中查找到达矩阵末尾所需的最小步数
假设我们有一个包含正整数的二维矩阵。如果我们位于单元格(i, j)，我们可以移动到单元格(i, j+mat[i, j]) 或 (i+mat[i, j], j)，我们需要找到从矩阵的起始位置(左上角单元格)到矩阵末尾(右下角单元格)所需的最小步数。我们不能越界。例如，矩阵如下所示：
| 2 | 1 | 2 |
| 1 | 1 | 1 |
| 1 | 1 | 1 |
输出将是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
更新于：2019年12月18日
343 次浏览
广告