এই সমস্যায়, আমাদের M*N আকারের একটি ২D ম্যাট্রিক্স দেওয়া আছে। আমাদের কাজ হল একটি প্রোগ্রাম তৈরি করা যা ম্যাট্রিক্সে সর্বোচ্চ পাথ সাম বের করবে।
এখানে, ম্যাট্রিক্সে সর্বোচ্চ পাথ সাম বলতে একটি রো থেকে লাস্ট রো পর্যন্ত সব উপাদানগুলোর যোগফল বোঝানো হয়েছে। পাথ ট্রভার্স করার জন্য অনুমোদিত মুভ হল ডাউনওয়ার্ড মুভ এবং ডায়াগোনাল মুভ। স্টার্ট এবং এন্ড পয়েন্ট ম্যাট্রিক্সের প্রথম এবং লাস্ট রোর যেকোনো উপাদান হতে পারে।
একটি উদাহরণ নিয়ে সমস্যাটি বুঝতে চাই
ইনপুট −
matrix [][] = 3 5 9 1 7 2 4 8 6
আউটপুট − 24
ব্যাখ্যা − সর্বোচ্চ পাথ হবে 9 → 7 → 8।
সমস্যাটি সমাধানের জন্য, আমরা অ্যারেতে উপরে থেকে শুরু করব এবং প্রথম রোর সর্বোচ্চ উপাদানটি বের করে maxSum-এ সংরক্ষণ করব। তারপর ম্যাট্রিক্স ট্রভার্স করে পাথে मिलने वाले সর্বোচ্চ মানগুলো বের করব। নতুন মানগুলো যদি বড় হয় তবে maxSum আপডেট করব অন্যথায় করব না। এবং পুরো ম্যাট্রিক্স ট্রভার্স হয়ে পাথ তৈরি হয়ে গেলে maxSum রিটার্ন করব।
উদাহরণ
ম্যাট্রিক্সে সর্বোচ্চ পাথ সাম বের করার প্রোগ্রাম −
#include <iostream> #define N 3 #define M 3 using namespace std; int maxPathSum(int mat[][M]){ for (int i = 1; i < N; i++) { for (int j = 0; j < M; j++) { if (j > 0 && j < M - 1) mat[i][j] += max(mat[i - 1][j], max(mat[i - 1][j - 1],mat[i - 1][j + 1])); else if (j > 0) mat[i][j] += max(mat[i - 1][j], mat[i - 1][j - 1]); else if (j < M - 1) mat[i][j] += max(mat[i - 1][j], mat[i - 1][j + 1]); } } int maxSum = mat[N-1][0]; for (int j = 1; j < M; j++) maxSum = max(mat[N-1][j], maxSum); return maxSum; } int main(){ int matrix[N][M] = { {3, 5, 9 }, {1, 7, 2}, {4, 8, 6}}; cout<<"The maximum path sum of matrix is : "<<maxPathSum(matrix); return 0; }
আউটপুট
The maximum path sum of matrix is : 24
