Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> Python

Python में भूलभुलैया मैट्रिक्स से बचने के लिए न्यूनतम चालें खोजने का प्रोग्राम

मान लीजिए हमारे पास एक बाइनरी मैट्रिक्स है, जहां 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 के अंत में डालें
  • -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
  1. पायथन में शतरंज के टुकड़े के लिए हर पोजीशन तक पहुंचने के लिए न्यूनतम चालें खोजने का प्रोग्राम पायथन में शतरंज के टुकड़े के लिए हर पोजीशन तक पहुंचने के लिए न्यूनतम चालें खोजने का प्रोग्राम

    मान लीजिए, हमारे पास एक शतरंज बोर्ड और एक विशेष नाइट पीस K है, जो बोर्ड के भीतर L आकार में चलता है। यदि पीस (x1, y1) स्थिति में है और यह (x2, y2) पर चलता है तो गति को इस प्रकार वर्णित किया जा सकता है: x2 = x1 ± a; y2 = y1 ± b या x2 = x1 ± b; y2 = y1 ± a; जहां a और b पूर्णांक हैं। हमें उस शतरंज के ट

  1. - पायथन में मैट्रिक्स घुमाएं (Rotate Matrix)

    मान लीजिए हमारे पास एक n x n 2D मैट्रिक्स है। हमें इस मैट्रिक्स को 90 डिग्री घड़ी की दिशा में घुमाना है। यदि मैट्रिक्स है: [[1, 5, 7], [9, 6, 3], [2, 1, 3]] तो आउटपुट होगा: [[2, 9, 1], [1, 6, 5], [3, 3, 7]] हल करने का तरीका temp_matrix := [], column := मैट्रिक्स की लंबाई - 1 प्रत्येक कॉलम के ल

  1. मैट्रिक्स में पूरी तरह से घिरे हुए द्वीपों की संख्या गिनने का पायथन प्रोग्राम मैट्रिक्स में पूरी तरह से घिरे हुए द्वीपों की संख्या गिनने का पायथन प्रोग्राम

    मान लीजिए हमारे पास एक बाइनरी मैट्रिक्स है। जहां 1 भूमि दर्शाता है और 0 पानी दर्शाता है। जैसा कि हम जानते हैं एक द्वीप 1 का समूह है जो एक साथ जुड़े हुए हैं जिसकी परिधि पानी से घिरी हुई है। हमें पूरी तरह से घिरे हुए द्वीपों की संख्या ढूंढनी है। उदाहरण के लिए, यदि इनपुट इस तरह है: तो आउटपुट 2 होगा,