দুটি ট্রাভার্সাল ব্যবহার করে একটি গ্রিডে সর্বাধিক পয়েন্ট সংগ্রহ করুন

প্রতিটি কক্ষে পয়েন্ট সহ একটি ম্যাট্রিক্স রয়েছে, কিভাবে দুটি ট্রাভার্সাল ব্যবহার করে সেই গ্রিড থেকে সর্বোচ্চ পয়েন্ট পেতে হয়৷

সন্তুষ্ট করার জন্য কিছু শর্ত আছে -

• প্রথম ট্রাভার্সাল গ্রিডের উপরের বাম ঘর থেকে শুরু হয় এবং নীচের বাম কোণে যেতে হবে। এবং দ্বিতীয় ট্রাভার্সালে উপরের ডান কোণ থেকে শুরু করে নীচের ডান কোণে
• একটি কোষ থেকে আমরা কেবলমাত্র বর্তমান কোষের নীচে, নীচের বাম দিকে এবং বর্তমান কোষগুলির নীচের ডানদিকে যেতে পারি৷
• যদি একটি ট্রাভার্সাল ইতিমধ্যেই একটি সেল থেকে কিছু পয়েন্ট পেয়ে থাকে, তাহলে পরবর্তী ট্রাভার্সালে সেই সেল থেকে কোনো পয়েন্ট পাওয়া যাবে না৷

ইনপুট এবং আউটপুট

ইনপুট:পয়েন্ট সহ একটি গ্রিড। 3 6 8 25 2 4 31 1 20 101 1 20 101 1 20 10 আউটপুট:দুটি ট্রাভার্সাল দ্বারা সংগৃহীত সর্বাধিক পয়েন্ট হল 73। প্রথম ট্রাভার্সাল থেকে, এটি লাভ করে:3 + 2 + 2 1 + 1 =27 দ্বিতীয় ট্রাভার্সাল থেকে, এটি লাভ করে:2 + 4 + 10 + 20 + 10 =46

অ্যালগরিদম

findMaxVal(mTable, x, y1, y2)

ইনপুট - একটি 3D অ্যারে মেমোরাইজেশন টেবিল, x মান এবং y1, y2।

আউটপুট - সর্বোচ্চ মান।

শুরু করুন যদি x, y1 এবং y2 বৈধ না হয়, তাহলে রিটার্ন করুন - ∞ যদি উভয় ট্রাভার্সাল সম্পূর্ণ হয়, তারপর যদি y1 =y2, তাহলে রিটার্ন গ্রিড[x, y1] অন্যথায় রিটার্ন গ্রিড[x, y1] + গ্রিড[x , y2] যদি উভয় ট্রাভার্সাল শেষ সারিতে থাকে, তাহলে রিটার্ন করুন - ∞ যদি সাবপ্রবলেম সলভ করা হয়, তাহলে ফিরুন mTable[x, y1, y2] সেট res :=- ∞ যদি y1 =y2, তারপর temp :=গ্রিড[x, y1 ] else temp :=গ্রিড[x, y1] + গ্রিড[x, y2] res :=res এর সর্বোচ্চ এবং (temp + findMaxVal(mTable, x+1, y1, y2-1)) res :=res এর সর্বোচ্চ এবং (temp + findMaxVal(mTable, x+1, y1, y2+1)) res :=res এর সর্বোচ্চ এবং (temp + findMaxVal(mTable, x+1, y1, y2)) res :=res এর সর্বোচ্চ এবং (temp + findMaxVal(mTable, x+1, y1-1, y2)) res :=res এর সর্বোচ্চ এবং (temp + findMaxVal(mTable, x+1, y1-1, y2-1)) res :=রেস এর সর্বোচ্চ এবং (temp + findMaxVal(mTable, x+1, y1-1, y2+1)) res :=রেস এর সর্বোচ্চ এবং (temp + FindMaxVal(mTable, x+1, y1+1, y2)) res :=সর্বাধিক res এবং (temp + findMaxVal(mTable, x+1, y1+1, y2-1)) res :=res এর সর্বোচ্চ এবং (temp + findMaxVal(mTable, x+1, y1+1, y2+1)) যদি mTable[x, y1, y2] =পুনরায় শেষ করে তাহলে সত্য ফেরত দেয়। 
উদাহরণ
 
#include#define ROW 5#define COL 4using namespace std;int grid[ROW][COL] ={ {3, 6, 8, 2}, {5, 2, 4, 3}, { 1, 1, 20, 10}, {1, 1, 20, 10}, {1, 1, 20, 10},};bool isValidInput(int x, int y1, int y2) { ফেরত (x>=0 &&x =0 &&y1 =0 &&y2 b)?a:b;}int findMaxVal( int mTable[ROW][COL][COL], int x, int y1, int y2) { if (!isValidInput(x, y1, y2)) //অবৈধ কক্ষে, রিটার্ন -ve ইনফিনিটি রিটার্ন INT_MIN; যদি (x ==ROW-1 &&y1 ==0 &&y2 ==COL-1) //যখন উভয় ট্রাভার্সাল সম্পূর্ণ রিটার্ন হয় (y1 ==y2)? গ্রিড[x][y1]:গ্রিড[x][y1] + গ্রিড[x][y2]; যদি (x ==ROW-1) // উভয় ট্রাভার্সাল শেষ সারিতে থাকে কিন্তু INT_MIN রিটার্ন সম্পূর্ণ না হয়; যদি (mTable[x][y1][y2] !=-1) //যখন সাব-সমস্যা সমাধান হয় mTable[x][y1][y2] ফেরত দেয়; int উত্তর =INT_MIN; //প্রাথমিকভাবে উত্তর হল -ve infinity int temp =(y1 ==y2)? গ্রিড[x][y1]:গ্রিড[x][y1] + গ্রিড[x][y2]; //বর্তমান ঘরের স্টোর লাভ //সকল সম্ভাব্য মানের জন্য উত্তর খুঁজুন এবং তার মধ্যে সর্বাধিক ব্যবহার করুন answer =max(উত্তর, temp + FindMaxVal(mTable, x+1, y1, y2-1)); উত্তর =সর্বোচ্চ(উত্তর, টেম্প + FindMaxVal(mTable, x+1, y1, y2+1)); উত্তর =সর্বোচ্চ(উত্তর, টেম্প + FindMaxVal(mTable, x+1, y1, y2)); উত্তর =সর্বোচ্চ(উত্তর, টেম্প + FindMaxVal(mTable, x+1, y1-1, y2)); উত্তর =সর্বোচ্চ(উত্তর, টেম্প + FindMaxVal(mTable, x+1, y1-1, y2-1)); উত্তর =সর্বোচ্চ(উত্তর, টেম্প + FindMaxVal(mTable, x+1, y1-1, y2+1)); উত্তর =সর্বোচ্চ(উত্তর, টেম্প + FindMaxVal(mTable, x+1, y1+1, y2)); উত্তর =সর্বোচ্চ(উত্তর, টেম্প + FindMaxVal(mTable, x+1, y1+1, y2-1)); উত্তর =সর্বোচ্চ(উত্তর, টেম্প + FindMaxVal(mTable, x+1, y1+1, y2+1)); ফেরত (mTable[x][y1][y2] =উত্তর); //উত্তরটি mTable-এ সঞ্চয় করুন এবং ফেরত দিন। for(int i =0; i 
আউটপুট
 
সর্বোচ্চ সংগ্রহ ৭৩