मान लीजिए हमारे पास N x 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) पर स्थित है, तो grid[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 := पंक्तियों की संख्या
यदि grid[0, 0] 0 है, तो एक नया पॉइंट p(0, 0, 1) बनाएं, p को q में सम्मिलित करें, और grid[0, 0] := 1 बनाएं
जब तक q खाली नहीं है
curr := q से फ्रंट पॉइंट, q से फ्रंट पॉइंट हटाएं
x := curr का x मान, y := curr का y मान, c := curr का c मान
यदि x = n - 1 और y = n - 1, तो c लौटाएं
c को 1 से बढ़ाएं
i को 0 से 7 तक के लिए
X := x + d[i, 0], Y := y + d[i, 1]
यदि X 0 और n की सीमा में है और Y 0 और n की सीमा में है, और grid[X, Y] 0 है, तो
grid[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;
}
};
int 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