C++ এ বাইনারি ম্যাট্রিক্সের সবচেয়ে ছোট পথ

ধরুন আমাদের একটি N বাই N বর্গাকার গ্রিড আছে, সেখানে প্রতিটি সেল হয় খালি (0) বা অবরুদ্ধ (1)। উপরে-বাম থেকে নীচে-ডানে একটি পরিষ্কার পথের দৈর্ঘ্য k থাকে যদি এবং শুধুমাত্র যদি এটি C_1, C_2, ..., C_k কোষ দ্বারা গঠিত হয় যাতে −

• সংলগ্ন কক্ষ C_i এবং C_{i+1} 8-দিকনির্দেশকভাবে সংযুক্ত (তাই তারা আলাদা এবং একটি প্রান্ত বা কোণ ভাগ করে)

• C_1 অবস্থানে (0, 0)

• C_k অবস্থানে (N-1, N-1)

• যদি C_i (r, c) এ অবস্থিত, তাহলে গ্রিড[r, c] খালি বা 0

  থাকে

আমাদের উপরে-বাম থেকে নীচে-ডান পর্যন্ত সংক্ষিপ্ততম যেমন পরিষ্কার পথের দৈর্ঘ্য খুঁজে বের করতে হবে। যদি এমন কোন পথ না থাকে, তাহলে ফিরুন -1।

উদাহরণস্বরূপ, যদি গ্রিড −

কমলা কোষের পথ হবে। দৈর্ঘ্য হল 4

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

• একটি দিক বিন্যাস সংজ্ঞায়িত করুন, এটি 8 টি ভিন্ন দিক সরানোর জন্য 8 জোড়া ধরে রাখবে। সুতরাং এই অ্যারেটি হল [[1,1], [1,-1], [-1,1], [1,0], [0,1], [-1,-1], [0,- 1], [-1,0]]

• প্রধান বিভাগটি গ্রিডটিকে ইনপুট হিসাবে গ্রহণ করবে, এটি নীচের মত কাজ করবে −

• পয়েন্টের একটি সারি নির্ধারণ করুন, q, n:=সারির সংখ্যা

• যদি গ্রিড[0, 0] 0 ​​হয়, তাহলে একটি নতুন বিন্দু তৈরি করুন p(0, 0, 1), q-তে p ঢোকান এবং গ্রিড তৈরি করুন [0, 0] :=1

• যখন q খালি নয়

  • curr :=q থেকে সামনের বিন্দু, q থেকে সামনের বিন্দু মুছে ফেলুন

  • x :=curr এর x মান, y :=curr এর y মান, c :=c curr এর মান

  • যদি x =n – 1 এবং y =n – 1 হয়, তাহলে c

    ফেরত দিন

  • 1 দ্বারা c বাড়ান

  • আমি 0 থেকে 7 রেঞ্জের জন্য

    • X :=x + d[i, 0], Y :=y + d[i, 1]

    • যদি 0 এবং n পরিসরে X এবং 0 এবং n পরিসরে y এবং গ্রিড[X, Y] 0 হয়, তাহলে

      • গ্রিড[X, Y] :=1

      • q

        -এ একটি নতুন বিন্দু p (X, Y, c) সন্নিবেশ করান

• রিটার্ন -1

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

উদাহরণ

#include <bits/stdc++.h>
using namespace std;
int d[8][2] = {{1, 1}, {1, -1}, {-1, 1}, {1, 0}, {0, 1}, {-1, -1},
{0, -1}, {-1, 0}};
struct point{
   int x, y, c;
   point(int a, int b, int z){
      x = a;
      y = b;
      c = z;
   }
};
class Solution {
   public:
   int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
      queue <point> q;
      int n = grid.size();
      if(!grid[0][0]){
         q.push(point(0, 0, 1));
         grid[0][0] = 1;
      }
      while(!q.empty()){
         point curr = q.front();
         q.pop();
         int x = curr.x;
         int y = curr.y;
         int c = curr.c;
         if(x == n-1 && y == n-1)return c;
            c++;
         for(int i = 0; i < 8; i++){
            int X = x + d[i][0];
            int Y = y + d[i][1];
            if(X >= 0 && X < n && Y >= 0 && Y < n &&
            !grid[X][Y]){
               grid[X][Y] = 1;
               q.push(point(X, Y, c));
            }
         }
      }
      return -1;
   }
};
main(){
   vector<vector<int>> v = {{0,0,0},{1,1,0},{1,1,0}};
   Solution ob;
   cout << (ob.shortestPathBinaryMatrix(v));
}

ইনপুট

[[0,0,0],[1,1,0],[1,1,0]]

আউটপুট

4