C++ में लेफ्ट, राइट, बॉटम और अप मूव्स के साथ मिनिमम कॉस्ट पाथ की अनुमति है

मान लीजिए कि हमारे पास 2D सरणी है। जहां प्रत्येक सेल में संख्या लागत होती है जो उस सेल के माध्यम से जाने की लागत का प्रतिनिधित्व करती है, हमें ऊपर-बाएं सेल से नीचे-दाएं सेल तक एक पथ खोजना होगा जिसके द्वारा खपत की गई कुल लागत न्यूनतम हो।

तो, अगर इनपुट पसंद है

तो आउटपुट 340 होगा (32 + 11 + 14 + 48 + 66 + 13 + 19 + 7 + 34 + 12 + 21 + 42 + 21) =340

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• x, y निर्देशांक और दूरी पैरामीटर के साथ सेल को परिभाषित करें।
• आकार के सरणी मैट्रिक्स को परिभाषित करें:पंक्ति x कॉलम।
• मैट्रिक्स को जानकारी से भरें
• एक सरणी dx आकार परिभाषित करें:4 :={ - 1, 0, 1, 0}
• एक सरणी डाई को आकार में परिभाषित करें:4 :={0, 1, 0, - 1}
• सेंट नामक सेल के एक सेट को परिभाषित करें
• सेंट में सेल(0, 0, 0) डालें
• मैट्रिक्स[0, 0] :=ग्रिड[0, 0]
• जबकि (सेंट खाली नहीं है), करें −
  • k :=सेंट का पहला तत्व
  • सेंट से सेंट का पहला तत्व हटाएं
  • इनिशियलाइज़ 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 के बराबर नहीं है, तो −
        • सेंट से सेल (x, y, matrix[x, y]) ढूंढें और हटाएं
      • मैट्रिक्स[x, y] :=मैट्रिक्स[k.x, k.y] + ग्रिड[x, y]
      • सेंट में सेल (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