গন্তব্যে পৌঁছানোর জন্য ন্যূনতম প্রাথমিক পয়েন্ট

একটি গ্রিডের উপরের বাম কোণ থেকে শুরু করে নিচের ডান কোণে পৌঁছাতে হবে। গ্রিডের প্রতিটি কক্ষ একটি সংখ্যা ধারণ করে যা ধনাত্মক বা ঋণাত্মক হতে পারে। কোনো কক্ষ (i, j) এ পৌঁছালে ব্যক্তির টোকেন সংখ্যা সেই কক্ষের মান অনুযায়ী বৃদ্ধি বা হ্রাস পায়। যাত্রা সম্পন্ন করার জন্য ন্যূনতম কতগুলো প্রাথমিক টোকেন প্রয়োজন তা বের করতে হবে।

নিয়মগুলো:

• শুধু ডানে বা নিচে যেতে পারবেন।
• আমাদের মোট টোকেন যদি (i, j) কক্ষের মান থেকে কম হয়, তবে সেখানে যেতে পারব না।
• গন্তব্যে ধনাত্মক পয়েন্ট নিয়ে পৌঁছাতে হবে।

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

ইনপুট: প্রতিটি কক্ষের টোকেন ম্যাট্রিক্স হিসেবে।
-2  -3  3
-5 -10  1
10  30 -5

আউটপুট: যাত্রা শুরু করার জন্য ন্যূনতম টোকেন। এই উদাহরণে প্রয়োজনীয় টোকেন ৭।

অ্যালগরিদম

minInitTokens(matrix)

ইনপুট: প্রতিটি কক্ষের টোকেন ম্যাট্রিক্স।
আউটপুট: শুরুর বিন্দু থেকে গন্তব্যে পৌঁছানোর জন্য ন্যূনতম টোকেন।

শুরু
  matrix-এর আকারের minToken ম্যাট্রিক্স সংজ্ঞায়িত করুন
  m := matrix-এর সারির সংখ্যা
  n := matrix-এর কলামের সংখ্যা
  যদি matrix[m-1, n-1] > 0 হয়, তবে
    minToken[m-1, n-1] := 0
  অন্যথায়
    minToken[m-1, n-1] := 1 + |matrix[m-1, n-1]|
  i := m-2 থেকে 0 পর্যন্ত নিচের দিকে, করুন
    minToken[i, n-1] := 1 এবং (minToken[i+1, n-1] - matrix[i,n-1]) এর মধ্যে সর্বোচ্চ
  শেষ
  j := n-2 থেকে 0 পর্যন্ত নিচের দিকে, করুন
    minToken[m-1, j] := 1 এবং (minToken[m-1, j+1] - matrix[m-1, j]) এর মধ্যে সর্বোচ্চ
  শেষ
  i := m-2 থেকে 0 পর্যন্ত নিচের দিকে, করুন
    j := n-2 থেকে 0 পর্যন্ত নিচের দিকে, করুন
      rem := minToken[i+1, j] এবং minToken[i, j+1] এর মধ্যে ন্যূনতম
      minToken[i, j] := 1 এবং (rem - matrix[i,j]) এর মধ্যে সর্বোচ্চ
    শেষ
  শেষ
  minToken[0, 0] ফেরত দিন
শেষ

উদাহরণ (C++)

#include <iostream>
#include <cmath>
#define ROW 3
#define COL 3
using namespace std;

int tokens[ROW][COL] = {
  {-2,-3,3},
  {-5,-10,1},
  {10,30,-5}
};

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

int minInitPoints() {
  int minToken[ROW][COL];
  int m = ROW, n = COL;
  minToken[m-1][n-1] = tokens[m-1][n-1] > 0 ? 1 : abs(tokens[m-1][n-1]) + 1;

  for (int i = m-2; i >= 0; i--)
    minToken[i][n-1] = max(minToken[i+1][n-1] - tokens[i][n-1], 1);

  for (int j = n-2; j >= 0; j--)
    minToken[m-1][j] = max(minToken[m-1][j+1] - tokens[m-1][j], 1);

  for (int i=m-2; i>=0; i--) {
    for (int j=n-2; j>=0; j--) {
      int remPoint = min(minToken[i+1][j], minToken[i][j+1]);
      minToken[i][j] = max(remPoint - tokens[i][j], 1);
    }
  }
  return minToken[0][0];
}

int main() {
  cout << "Minimum Points Required: " << minInitPoints();
}

আউটপুট

Minimum Points Required: 7