C++ में बाइनरी मैट्रिक्स में सबसे छोटा पथ

मान लीजिए कि हमारे पास एन से एन वर्ग ग्रिड है, वहां प्रत्येक सेल या तो खाली है (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) पर स्थित है, तो grid[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) बनाएं, p को q में डालें, और ग्रिड बनाएं[0, 0] :=1

• जबकि q खाली नहीं है

  • curr :=q से सामने का बिंदु, q से सामने का बिंदु हटाएं

  • x :=curr का मान, y :=y curr का मान, c :=c curr का मान

  • अगर x =n – 1 और y =n – 1 है, तो वापस c

  • c को 1 से बढ़ाएँ

  • मेरे लिए 0 से 7 की सीमा में

    • एक्स:=एक्स + डी [i, 0], वाई:=वाई + डी [i, 1]

    • यदि X श्रेणी में 0 और n और y श्रेणी 0 और n में है, और ग्रिड [X, Y] 0 है, तो

      • ग्रिड [एक्स, वाई] :=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