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

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

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

0	0	0
1	1	0
0	0	0
0	1	1
0	0	0

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

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

फ़ंक्शन को परिभाषित करें ठीक (), यह जांच करेगा कि x और y श्रेणी r और c में हैं या नहीं
50 x 50 x 2000 आकार की एक सरणी डीपी परिभाषित करें
एक डेटा संरचना को परिभाषित करें जहां x, y, k और लंबाई मौजूद हैं।
मुख्य विधि से निम्न कार्य करें -
dp को inf से भरें
r :=पंक्ति गणना, c :=स्तंभ गणना
एक कतार को परिभाषित करें q
रूट नामक डेटा ऑब्जेक्ट बनाएं (x =0, y =0, k, लंबाई =0)
q में रूट डालें
जबकि (नहीं q खाली है), करें -
- नोड:=q का पहला तत्व
- q से तत्व हटाएं
- x :=node.x, y :=node.y, k :=node.k, length :=node.length
- यदि x, r-1 के समान है और y, c-1 के समान है, तो -
  - वापसी की लंबाई
- (लंबाई 1 से बढ़ाएं)
- इनिशियलाइज़ करने के लिए मैं :=0, जब i <4, अपडेट (i 1 से बढ़ाएँ), करें -
  - एनएक्स:=एक्स + डीआईआर [i, 0]
  - ny :=y + dir[i, 1]
  - यदि nx, r-1 के समान है और ny, c-1 के समान है, तो -
    - वापसी की लंबाई
  - अगर ठीक है (एनएक्स, एनवाई, आर, सी) सच है, तो -
    - अगर ग्रिड [एनएक्स, एनवाई] 0 के समान है, तो -
      - अगर लंबाई
        
        (x =nx, y =ny, k, लंबाई) के साथ q
        में नया डेटा ऑब्जेक्ट डालें
        
        डीपी [एनएक्स, एनवाई, के]:=लंबाई
    - अन्यथा
      - अगर k> 0 और लंबाई
        
        (x =nx, y =ny, k =k-1,length) के साथ q
        में नया डेटा ऑब्जेक्ट डालें
        
        डीपी [एनएक्स, एनवाई, के]:=लंबाई
वापसी -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;
   }
};
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));
}

इनपुट

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