मान लीजिए हमारे पास एक 2D ग्रिड है जो एक भूलभुलैया को दर्शाता है जहां 0 खाली स्थान के लिए है, और 1 दीवार है। हम grid[0, 0] से शुरू करेंगे, हमें ग्रिड के निचले दाएं कोने तक पहुंचने के लिए वर्गों की न्यूनतम संख्या ढूंढनी होगी। यदि हम पहुंच नहीं सकते, तो -1 लौटाएं।
तो, यदि इनपुट इस तरह है
| 0 | 0 | 0 |
| 1 | 0 | 0 |
| 1 | 0 | 0 |
तो आउटपुट 5 होगा।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे:
- R := ग्रिड की पंक्ति संख्या, C := ग्रिड की कॉलम संख्या
- q := [0, 0, 1] यदि A[0, 0] 1 है अन्यथा एक नई सूची
- A[0, 0] := 1
- q में प्रत्येक (r, c, d) के लिए, करें
- यदि (r, c), (R-1, C-1) के समान है, तो d लौटाएं
- प्रत्येक (x, y) में [(r+1, c), (r-1, c), (r, c+1), (r, c-1)] के लिए, करें
- यदि x 0 से R की रेंज में है और y 0 से C की रेंज में है और A[x, y], 0 के समान है, तो
- A[x, y] := 1
- (x, y, d+1) को q के अंत में डालें
- यदि x 0 से R की रेंज में है और y 0 से C की रेंज में है और A[x, y], 0 के समान है, तो
- -1 लौटाएं
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:
उदाहरण
class Solution:
def solve(self, A):
R, C = len(A), len(A[0])
q = [(0, 0, 1)] if not A[0][0] else []
A[0][0] = 1
for r, c, d in q:
if (r, c) == (R - 1, C - 1):
return d
for x, y in [(r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)]:
if 0 <= x < R and 0 <= y < C and A[x][y] == 0:
A[x][y] = 1
q.append((x, y, d + 1))
return -1
ob = Solution()
grid = [
[0, 0, 0],
[1, 0, 0],
[1, 0, 0]
]
print(ob.solve(grid))
इनपुट
grid = [ [0, 0, 0], [1, 0, 0], [1, 0, 0] ]
आउटपुट
5