C++ এ বাধা দূরীকরণ সহ একটি গ্রিডে সংক্ষিপ্ততম পথ

ধরুন আমাদের একটি m x n গ্রিড আছে, এখানে প্রতিটি সেল হয় 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)।

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

একটি ফাংশন ok() সংজ্ঞায়িত করুন, এটি পরীক্ষা করবে যে x এবং y r এবং c রেঞ্জে আছে কি না
50 x 50 x 2000 আকারের একটি অ্যারে ডিপি সংজ্ঞায়িত করুন
একটি ডেটা কাঠামো সংজ্ঞায়িত করুন যেখানে x, y, k এবং দৈর্ঘ্য উপস্থিত রয়েছে।
প্রধান পদ্ধতি থেকে নিম্নলিখিতগুলি করুন -
inf দিয়ে dp পূরণ করুন
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 দ্বারা দৈর্ঘ্য বাড়ান)
- আরম্ভ করার জন্য i :=0, যখন i <4, আপডেট করুন (i 1 দ্বারা বাড়ান), করবেন −
  - nx :=x + dir[i, 0]
  - ny :=y + dir[i, 1]
  - যদি nx r - 1 এবং ny হয় c - 1 এর সমান, তাহলে −
    - রিটার্ন দৈর্ঘ্য
  - যদি ok(nx, ny, r, c) সত্য হয়, তাহলে −
    - যদি গ্রিড[nx, ny] 0 এর মত হয়, তাহলে −
      - যদি দৈর্ঘ্য
        
        q তে (x =nx, y =ny, k, দৈর্ঘ্য) দিয়ে নতুন ডেটা অবজেক্ট সন্নিবেশ করুন
        
        dp[nx, ny, k] :=দৈর্ঘ্য
    - অন্যথায়
      - যদি k> 0 এবং দৈর্ঘ্য
        
        q এ (x =nx, y =ny, k =k - 1, দৈর্ঘ্য) দিয়ে নতুন ডেটা অবজেক্ট সন্নিবেশ করুন
        
        dp[nx, ny, k] :=দৈর্ঘ্য
রিটার্ন -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}}