पायथन में भूलभुलैया मैट्रिक्स से बचने के लिए न्यूनतम चालें

मान लीजिए कि हमारे पास एक बाइनरी मैट्रिक्स है, जहां 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 होगा क्योंकि, हम −

. जैसे पथ का चयन कर सकते हैं

0	0	0	1	0
0	0	1	1	0
0	0	0	1	1
1	1	0	0	0

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

R :=पंक्तियों की संख्या
C :=स्तंभों की संख्या
q :=एक खाली सूची, प्रारंभ में डालें (0, 0, 1) यदि मैट्रिक्स [0, 0] 0 है
मैट्रिक्स[0, 0] :=1
क्यू में प्रत्येक ट्रिपलेट (आर, सी, डी) के लिए, करें
- अगर (आर, सी) (आर -1, सी -1) के समान है, तो
  - वापसी d
- प्रत्येक x के लिए, y in [(r + 1, c) ,(r - 1, c) ,(r, c + 1) ,(r, c - 1)], do
  - यदि 0 <=x
  - मैट्रिक्स[x, y] :=1
  - q के अंत में ट्रिपलेट (x, y, d + 1) डालें

वापसी -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]
]