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