मान लीजिए हमारे पास एक बाइनरी मैट्रिक्स है, जहां 0 एक खाली सेल दर्शाता है, और 1 एक दीवार है। यदि हम ऊपरी बाएं कोने (0, 0) से शुरू करते हैं, तो हमें निचले दाएं कोने (R-1, C-1) तक पहुंचने के लिए न्यूनतम सेल्स की संख्या ज्ञात करनी है। यहां R पंक्तियों की संख्या है और C स्तंभों की संख्या है। यदि कोई उत्तर नहीं मिलता है, तो -1 लौटाएं।
इसलिए, यदि इनपुट है [[0,0,0,1,0],[0,0,1,1,0],[0,0,0,1,1],[1,1,0,0,0]] तो आउटपुट 8 होगा क्योंकि हम निम्न पथ चुन सकते हैं।
हल करने का दृष्टिकोण
- R := पंक्तियों की संख्या
- C := स्तंभों की संख्या
- q := एक खाली सूची, प्रारंभ में (0, 0, 1) डालें यदि matrix[0, 0] 0 है
- matrix[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)] में, करें:
- यदि 0 <= x < R और 0 <= y < C और matrix[x, y] 0 के समान है, तो:
- matrix[x, y] := 1
- ट्रिपल (x, y, d+1) को q के अंत में डालें
- यदि 0 <= x < R और 0 <= y < C और matrix[x, y] 0 के समान है, तो:
- -1 लौटाएं
उदाहरण
def solve(matrix):
R, C = len(matrix), len(matrix[0])
q = [(0, 0, 1)] if not matrix[0][0] else []
matrix[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 matrix[x][y] == 0:
matrix[x][y] = 1
q.append((x, y, d + 1))
return -1
matrix = [
[0, 0, 0, 1, 0],
[0, 0, 1, 1, 0],
[0, 0, 0, 1, 1],
[1, 1, 0, 0, 0]
]
print(solve(matrix))
इनपुट
[[0, 0, 0, 1, 0], [0, 0, 1, 1, 0], [0, 0, 0, 1, 1], [1, 1, 0, 0, 0]]
आउटपुट
8