C++ এ অনুমোদিত বাম, ডান, নীচে এবং উপরে চলার সাথে ন্যূনতম খরচের পথ

ধরুন আমাদের একটি 2D অ্যারে আছে। যেখানে প্রতিটি কক্ষের সংখ্যা খরচ থাকে যা সেই কক্ষের মাধ্যমে পরিদর্শন করার খরচকে উপস্থাপন করে, আমাদের উপরের-বাম কক্ষ থেকে নীচে-ডান কক্ষে একটি পথ খুঁজে বের করতে হবে যার দ্বারা মোট খরচ সর্বনিম্ন।

সুতরাং, যদি ইনপুট মত হয়

তাহলে আউটপুট 340 হবে (32 + 11 + 14 + 48 + 66 + 13 + 19 + 7 + 34 + 12 + 21 + 42 + 21) =340

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• x, y স্থানাঙ্ক এবং দূরত্বের প্যারামিটার দিয়ে ঘরকে সংজ্ঞায়িত করুন।
• আকারের একটি অ্যারে ম্যাট্রিক্স সংজ্ঞায়িত করুন:সারি x কল।
• inf দিয়ে ম্যাট্রিক্স পূরণ করুন
• আকারের একটি অ্যারে dx সংজ্ঞায়িত করুন:4 :={ - 1, 0, 1, 0
• আকারের একটি অ্যারে dy সংজ্ঞায়িত করুন:4 :={0, 1, 0, - 1
• স্ট নামক কোষের একটি সেট সংজ্ঞায়িত করুন
• স্ট-এ সেল (0, 0, 0) ঢোকান
• ম্যাট্রিক্স[0, 0] :=গ্রিড[0, 0]
• যখন (st খালি নয়), −
  করুন
  • k :=st এর প্রথম উপাদান
  • st থেকে st-এর প্রথম উপাদান মুছুন
  • আরম্ভ করার জন্য i :=0, যখন i <4, আপডেট করুন (i 1 দ্বারা বৃদ্ধি করুন), −
    করুন
    • x :=k.x + dx[i]
    • y :=k.y + dy[i]
    • যদি না হয় ঠিক আছে(x, y), তাহলে −
      • নিম্নলিখিত অংশ উপেক্ষা করুন, পরবর্তী পুনরাবৃত্তিতে যান
    • যদি ম্যাট্রিক্স[x, y]> ম্যাট্রিক্স[k.x, k.y] + গ্রিড[x, y] হয়, তাহলে −
      • যদি ম্যাট্রিক্স[x, y] inf এর সমান না হয়, তাহলে −
        • st থেকে সেল (x, y, matrix[x, y]) খুঁজুন এবং মুছুন
      • ম্যাট্রিক্স[x, y] :=ম্যাট্রিক্স[k.x, k.y] + গ্রিড[x, y]
      • st-এ সেল (x, y, ম্যাট্রিক্স[x, y]) ঢোকান
• রিটার্ন ম্যাট্রিক্স[সারি - 1, কল - 1]

উদাহরণ

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

#include <bits/stdc++.h>
using namespace std;
#define ROW 5
#define COL 5
class cell {
   public:
   int x, y;
   int distance;
   cell(int x, int y, int distance) :
   x(x), y(y), distance(distance) {}
};
bool operator<(const cell& a, const cell& b) {
   if (a.distance == b.distance) {
      if (a.x != b.x)
         return (a.x < b.x);
      else
         return (a.y < b.y);
   }
   return (a.distance < b.distance);
}
bool isOk(int i, int j) {
   return (i >= 0 && i < COL && j >= 0 && j < ROW);
}
int solve(int grid[ROW][COL], int row, int col) {
   int matrix[row][col];
   for (int i = 0; i < row; i++)
   for (int j = 0; j < col; j++)
   matrix[i][j] = INT_MAX;
   int dx[] = {-1, 0, 1, 0};
   int dy[] = {0, 1, 0, -1};
   set<cell> st;
   st.insert(cell(0, 0, 0));
   matrix[0][0] = grid[0][0];
   while (!st.empty()) {
      cell k = *st.begin();
      st.erase(st.begin());
      for (int i = 0; i < 4; i++) {
         int x = k.x + dx[i];
         int y = k.y + dy[i];  
         if (!isOk(x, y))
            continue;
         if (matrix[x][y] > matrix[k.x][k.y] + grid[x][y]){
            if (matrix[x][y] != INT_MAX)
               st.erase(st.find(cell(x, y, matrix[x][y])));
               matrix[x][y] = matrix[k.x][k.y] + grid[x][y];
               st.insert(cell(x, y, matrix[x][y]));
         }
      }
   }
   return matrix[row - 1][col - 1];
}
int main() {
   int grid[ROW][COL] = {
      32, 101, 66, 13, 19,
      11, 14, 48, 158, 7,
      101, 114, 175, 12, 34,
      89, 126, 42, 21, 141,
      100, 33, 112, 42, 21
   };
   cout << solve(grid, ROW, COL);
}

ইনপুট

{32, 101, 66, 13, 19,
11, 14, 48, 158, 7,
101, 114, 175, 12, 34,
89, 126, 42, 21, 141,
100, 33, 112, 42, 21
};

আউটপুট:

340