ম্যাট্রিক্সের শেষ কোষ্ঠক পর্যন্ত যেতে ন্যূনতম ধাপ বের করা C++-তে

মনে করুন আমাদের ধনাত্মক পূর্ণসংখ্যাগুলোর একটি ২D ম্যাট্রিক্স আছে। আমাদের ম্যাট্রিক্সের শেষ কোষ্ঠক (ডানদিকের নিচের কোষ্ঠক) পর্যন্ত যেতে ন্যূনতম ধাপ বের করতে হবে। যদি আমরা কোষ্ঠক (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 && 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