দেওয়া সীমাবদ্ধতায় ম্যাট্রিক্সে সবচেয়ে বড় পথ খুঁজে বের করা C++-তে

মনে করুন আমাদের n ক্রমের একটি বর্গাকার ম্যাট্রিক্স আছে। এতে সব ভিন্ন উপাদান আছে। তাই আমাদের সর্বোচ্চ দৈর্ঘ্যের পথ বের করতে হবে, যেন পথের সকল কোষ্ঠক উর্ধ্বমুখী ক্রমে ১-এর পার্থক্য সহ থাকে। একটি কোষ্ঠক থেকে চার দিকে যাওয়া যাবে। বাম, ডান, উপর এবং নিচ। তাই যদি ম্যাট্রিক্সটি হয় -

তবে আউটপুট হবে 4। কারণ সবচেয়ে বড় পথ হল 6→7→8→9

এই সমস্যাটি সমাধানের জন্য, আমরা এই আইডিয়া অনুসরণ করব। আমরা প্রতিটি কোষ্ঠক থেকে শুরু হয়ে সবচেয়ে বড় পথ হিসাব করব। একবার সব কোষ্ঠকের জন্য সবচেয়ে বড় পথ পেলে, আমরা সবচেয়ে বড় পথের মধ্যে সর্বোচ্চটি রিটার্ন করব।

এই পদ্ধতিতে একটি গুরুত্বপূর্ণ পর্যবেক্ষণ হল অনেক ওভারল্যাপিং সাব-প্রობ্লেম। তাই এই সমস্যাটি ডাইনামিক প্রোগ্রামিং দিয়ে সমাধান করা যায়। এখানে আমরা একটি লুকআপ টেবিল dp[][] ব্যবহার করব যেন কোনো সমস্যা ইতিমধ্যে সমাধান করা হয়েছে কিনা চেক করা যায়।

উদাহরণ

#include <iostream>
#define n 3
using namespace std;

int getLongestPathLengthUtil(int i, int j, int matrix[n][n], int table[n][n]) {
    if (i < 0 || i >= n || j < 0 || j >= n)
        return 0;
    if (table[i][j] != -1)
        return table[i][j];
    int x = INT_MIN, y = INT_MIN, z = INT_MIN, w = INT_MIN;
    if (j < n - 1 && ((matrix[i][j] + 1) == matrix[i][j + 1]))
        x = 1 + getLongestPathLengthUtil(i, j + 1, matrix, table);
    if (j > 0 && (matrix[i][j] + 1 == matrix[i][j - 1]))
        y = 1 + getLongestPathLengthUtil(i, j - 1, matrix, table);
    if (i > 0 && (matrix[i][j] + 1 == matrix[i - 1][j]))
        z = 1 + getLongestPathLengthUtil(i - 1, j, matrix, table);
    if (i < n - 1 && (matrix[i][j] + 1 == matrix[i + 1][j]))
        w = 1 + getLongestPathLengthUtil(i + 1, j, matrix, table);
    return table[i][j] = max(x, max(y, max(z, max(w, 1))));
}

int getLongestPathLength(int matrix[n][n]) {
    int result = 1;
    int table[n][n];
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            table[i][j] = -1;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (table[i][j] == -1)
                getLongestPathLengthUtil(i, j, matrix, table);
            result = max(result, table[i][j]);
        }
    }
    return result;
}

int main() {
    int mat[n][n] = { { 1, 2, 9 }, { 5, 3, 8 }, { 4, 6, 7 } };
    cout << "Length of the longest path is " << getLongestPathLength(mat);
}

আউটপুট

Length of the longest path is 4