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

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

শর্তাবলী

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

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

ইনপুট: পয়েন্টসহ একটি গ্রিড।
3 6 8 2
5 2 4 3
1 1 20 10
1 1 20 10
1 1 20 10

আউটপুট: দুটি ট্রাভার্সাল দ্বারা সংগৃহীত সর্বোচ্চ পয়েন্ট ৭৩।
প্রথম ট্রাভার্সাল থেকে লাভ: 3 + 2 + 20 + 1 + 1 = 27
দ্বিতীয় ট্রাভার্সাল থেকে লাভ: 2 + 4 + 10 + 20 + 10 = 46

অ্যালগরিদম

findMaxVal(mTable, x, y1, y2)

ইনপুট: একটি ৩D অ্যারে মেমোরাইজেশন টেবিল হিসেবে, x মান এবং y1, y2।
আউটপুট: সর্বোচ্চ মান।

শুরু
  যদি x, y1 এবং y2 বৈধ না হয়, তবে
    ফেরত দিন -∞
  যদি দুটি ট্রাভার্সালই সম্পূর্ণ হয়, তবে
    যদি y1 = y2 হয়, তবে
      ফেরত দিন grid[x, y1]
    অন্যথায়
      ফেরত দিন grid[x, y1] + grid[x, y2]
  যদি দুটি ট্রাভার্সালই শেষ সারিতে থাকে, তবে
    ফেরত দিন -∞
  যদি উপসমস্যা সমাধান করা হয়ে থাকে, তবে
    ফেরত দিন mTable[x, y1, y2]
  res := -∞ সেট করুন
  যদি y1 = y2 হয়, তবে
    temp := grid[x, y1]
  অন্যথায়
    temp := grid[x, y1] + grid[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 := res এবং (temp + findMaxVal(mTable, x+1, y1-1, y2+1)) এর মধ্যে সর্বোচ্চ
  res := 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] = res সেট করুন
  ফেরত দিন true
শেষ

উদাহরণ (C++)

#include <iostream>
#define ROW 5
#define COL 4
using 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) {
  return (x >= 0 && x < ROW && y1 >= 0 && y1 < COL && y2 >= 0 && y2 < COL);
}

int max(int a, int b) {
  return (a > b) ? a : b;
}

int findMaxVal(int mTable[ROW][COL][COL], int x, int y1, int y2) {
  if (!isValidInput(x, y1, y2))
    return INT_MIN;

  if (x == ROW-1 && y1 == 0 && y2 == COL-1)
    return (y1 == y2) ? grid[x][y1] : grid[x][y1] + grid[x][y2];

  if (x == ROW-1)
    return INT_MIN;

  if (mTable[x][y1][y2] != -1)
    return mTable[x][y1][y2];

  int answer = INT_MIN;
  int temp = (y1 == y2) ? grid[x][y1] : grid[x][y1] + grid[x][y2];

  answer = max(answer, temp + findMaxVal(mTable, x+1, y1, y2-1));
  answer = max(answer, temp + findMaxVal(mTable, x+1, y1, y2+1));
  answer = max(answer, temp + findMaxVal(mTable, x+1, y1, y2));
  answer = max(answer, temp + findMaxVal(mTable, x+1, y1-1, y2));
  answer = max(answer, temp + findMaxVal(mTable, x+1, y1-1, y2-1));
  answer = max(answer, temp + findMaxVal(mTable, x+1, y1-1, y2+1));
  answer = max(answer, temp + findMaxVal(mTable, x+1, y1+1, y2));
  answer = max(answer, temp + findMaxVal(mTable, x+1, y1+1, y2-1));
  answer = max(answer, temp + findMaxVal(mTable, x+1, y1+1, y2+1));

  return (mTable[x][y1][y2] = answer);
}

int findMaxCollection() {
  int mTable[ROW][COL][COL];
  for(int i = 0; i < ROW; i++)
    for(int j = 0; j < COL; j++)
      for(int k = 0; k < COL; k++)
        mTable[i][j][k] = -1;

  return findMaxVal(mTable, 0, 0, COL-1);
}

int main() {
  cout << "Maximum collection is " << findMaxCollection();
  return 0;
}

আউটপুট

Maximum collection is 73