Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में बाएं, दाएं, नीचे और ऊपर की चालों की अनुमति के साथ न्यूनतम लागत पथ

समस्या विवरण

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

उदाहरण

32101661319
1114481587
1011141751234
891264221141
100331124221

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

एल्गोरिदम चरण

  • x, y निर्देशांक और दूरी पैरामीटर के साथ सेल परिभाषित करें।
  • आकार: पंक्ति x कॉलम की मैट्रिक्स सरणी परिभाषित करें।
  • मैट्रिक्स को अनंत से भरें
  • आकार 4 के dx सरणी := { -1, 0, 1, 0 } परिभाषित करें
  • आकार 4 के dy सरणी := {0, 1, 0, -1 } परिभाषित करें
  • सेल नामक एक सेट परिभाषित करें
  • सेल(0, 0, 0) को st में डालें
  • matrix[0][0] := grid[0][0]
  • जब तक st खाली नहीं है:
    • k := st का पहला तत्व
    • st से पहला तत्व हटाएं
    • i := 0 से 3 तक लूप करें:
      • x := k.x + dx[i]
      • y := k.y + dy[i]
      • यदि isOk(x, y) नहीं है, तो अगले पुनरावृत्ति पर जाएं
      • यदि matrix[x][y] > matrix[k.x][k.y] + grid[x][y]:
        • यदि matrix[x][y] अनंत के बराबर नहीं है, तो st से सेल(x, y, matrix[x][y]) ढूंढें और हटाएं
        • matrix[x][y] := matrix[k.x][k.y] + grid[x][y]
        • सेल(x, y, matrix[x][y]) को st में डालें
  • matrix[row - 1][col - 1] वापस करें

C++ कार्यान्वयन

#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
  1. C++ में न्यूनतम नाइट मूव्स C++ में न्यूनतम नाइट मूव्स

    मान लीजिए हमारे पास एक अनंत शतरंज बोर्ड है जिसके कोऑर्डिनेट्स -इनफिनिटी से +इनफिनिटी तक हैं, और हमारे पास [0, 0] स्क्वायर पर एक नाइट है। नाइट के 8 संभावित मूव्स होते हैं, जैसा कि नीचे दिखाया गया है। प्रत्येक मूव कार्डिनल डायरेक्शन में दो स्क्वायर, फिर ऑर्थोगोनल डायरेक्शन में एक स्क्वायर होता है। ह

  1. - C++ ऑपरेटर्स प्रीसिडेंस और असोसिएटिविटी के साथ

    ऑपरेटर प्रीसिडेंस एक अभिव्यक्ति में पदों के समूह को निर्धारित करता है। एक ऑपरेटर की असोसिएटिविटी एक गुण है जो निर्धारित करता है कि समान प्रीसिडेंस के ऑपरेटर्स को पैरेंथेसिस की अनुपस्थिति में कैसे समूहित किया जाता है। यह प्रभावित करता है कि एक अभिव्यक्ति का मूल्यांकन कैसे किया जाता है। कुछ ऑपरेटर्स

  1. - C++ में ऑपरेटर्स प्रीसिडेंस

    ऑपरेटर प्रीसिडेंस एक अभिव्यक्ति में पदों के समूह को निर्धारित करता है। एक ऑपरेटर की असोसिएटिविटी एक गुण है जो निर्धारित करता है कि समान प्रीसिडेंस के ऑपरेटर्स को पैरेंथेसिस की अनुपस्थिति में कैसे समूहित किया जाता है। यह प्रभावित करता है कि एक अभिव्यक्ति का मूल्यांकन कैसे किया जाता है। कुछ ऑपरेटर्स