ধরুন আমাদের একটি 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।
উদাহরণস্বরূপ, যদি গ্রিড −
এর মত হয়0 | 0 | 0 |
1 | 1 | 0 |
1 | 1 | 0 |
কমলা কোষের পথ হবে। দৈর্ঘ্য হল 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