資料結構
網路
關係資料庫管理系統 (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 次瀏覽
廣告