C++ में बाधा उन्मूलन के साथ ग्रिड में सबसे छोटा पथ

मान लीजिए हमारे पास एक m x n ग्रिड है, यहां प्रत्येक सेल या तो 0 या 1 है। 0 सेल खाली है और 1 अवरुद्ध है। एक चरण में, हम ऊपर, नीचे, बाएं या दाएं एक खाली सेल से और खाली सेल पर जा सकते हैं। हमें ऊपरी बाएं कोने सेल (0, 0) से निचले दाएं कोने सेल (m-1, n-1) तक चलने के लिए न्यूनतम चरणों की संख्या ज्ञात करनी है, यह देखते हुए कि हम अधिकतम k बाधाओं को समाप्त कर सकते हैं। यदि ऐसा कोई रास्ता नहीं है, तो -1 लौटाएं।

यदि इनपुट है -

और k = 1 है, तो आउटपुट 6 होगा, क्योंकि बिना किसी बाधा को समाप्त किए सबसे छोटा पथ 10 है। स्थिति (3,2) पर एक बाधा उन्मूलन के साथ सबसे छोटा पथ 6 होगा। ऐसा पथ होगा (0,0) से (0,1) से (0,2) से (1,2) से (2,2) से (3,2) से (4,2)।

हल करने के चरण

• ok() फ़ंक्शन परिभाषित करें जो जांचता है कि x और y सीमा r और c में हैं या नहीं

• आकार 50 x 50 x 2000 का एक सरणी dp परिभाषित करें

• Data संरचना परिभाषित करें जहां x, y, k और length मौजूद हैं

• मुख्य विधि से: dp को INF से भरें, कतार q परिभाषित करें, रूट डेटा ऑब्जेक्ट बनाएं

• BFS करें: यदि गंतव्य पहुंच गया तो लंबाई लौटाएं

• चार दिशाओं में जाएं: यदि खाली सेल है और लंबाई कम है तो कतार में डालें, यदि बाधा है और k > 0 तो k-1 के साथ कतार में डालें

• यदि कतार खाली हो जाए तो -1 लौटाएं

उदाहरण

#include <bits/stdc++.h> 
using namespace std; 

int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; 
int dp[50][50][2000]; 

struct Data { 
    int x, y, k, length; 
    Data(int a, int b, int c, int d) { 
        x = a; y = b; k = c; length = d; 
    } 
}; 

class Solution { 
public: 
    void pre() { 
        for (int i = 0; i < 50; i++) { 
            for (int j = 0; j < 50; j++) { 
                for (int k = 0; k < 2000; k++) { 
                    dp[i][j][k] = INT_MAX; 
                } 
            } 
        } 
    } 
    bool ok(int x, int y, int r, int c) { 
        return (x < r && y < c && x >= 0 && y >= 0); 
    } 
    int shortestPath(vector<vector<int> >& grid, int k) { 
        pre(); 
        int r = grid.size(); 
        int c = grid[0].size(); 
        queue<Data> q; 
        Data root(0, 0, k, 0); 
        q.push(root); 
        while (!q.empty()) { 
            Data node = q.front(); 
            q.pop(); 
            int x = node.x; 
            int y = node.y; 
            int k = node.k; 
            int length = node.length; 
            if (x == r - 1 && y == c - 1) return length; 
            length++; 
            for (int i = 0; i < 4; i++) { 
                int nx = x + dir[i][0]; 
                int ny = y + dir[i][1]; 
                if (nx == r - 1 && ny == c - 1) return length; 
                if (ok(nx, ny, r, c)) { 
                    if (grid[nx][ny] == 0) { 
                        if (length < dp[nx][ny][k]) { 
                            q.push(Data(nx, ny, k, length)); 
                            dp[nx][ny][k] = length; 
                        } 
                    } else { 
                        if (k > 0 && length < dp[nx][ny][k]) { 
                            q.push(Data(nx, ny, k - 1, length)); 
                            dp[nx][ny][k] = length; 
                        } 
                    } 
                } 
            } 
        } 
        return -1; 
    } 
}; 

int main() { 
    Solution ob; 
    vector<vector<int>> v = {{0,0,0},{1,1,0},{0,0,0},{0,1,1},{0,0,0}}; 
    cout << (ob.shortestPath(v, 1)); 
    return 0; 
}

इनपुट

{{0,0,0},{1,1,0},{0,0,0},{0,1,1},{0,0,0}}

आउटपुट

6