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

Python में निचले दाएं कोने तक पहुंचने के लिए आवश्यक न्यूनतम सेल्स की संख्या खोजने का प्रोग्राम


मान लीजिए हमारे पास एक 2D ग्रिड है जो एक भूलभुलैया को दर्शाता है जहां 0 खाली स्थान के लिए है, और 1 दीवार है। हम grid[0, 0] से शुरू करेंगे, हमें ग्रिड के निचले दाएं कोने तक पहुंचने के लिए वर्गों की न्यूनतम संख्या ढूंढनी होगी। यदि हम पहुंच नहीं सकते, तो -1 लौटाएं।

तो, यदि इनपुट इस तरह है

000
100
100

तो आउटपुट 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 के अंत में डालें
  • -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
  1. पायथन में मर्जिंग के बाद न्यूनतम रंगों की संख्या खोजने का प्रोग्राम पायथन में मर्जिंग के बाद न्यूनतम रंगों की संख्या खोजने का प्रोग्राम

    मान लीजिए हमारे पास रंगों (R, G, B) की एक लिस्ट है। अब यदि दो अलग-अलग रंग अगल-बगल हैं तो वे तीसरे रंग के एकल रंग आइटम में बदल सकते हैं। हमें किसी भी संभावित परिवर्तन अनुक्रम के बाद शेष सबसे छोटी संख्या ढूंढनी है।उदाहरण के लिए, यदि इनपुट colors = [G, R, G, B, R] है, तो आउटपुट 1 होगा क्योंकि यह नीचे द

  1. सभी पेड़ों को जलाने में लगने वाले दिनों की संख्या ज्ञात करने का पायथन प्रोग्राम सभी पेड़ों को जलाने में लगने वाले दिनों की संख्या ज्ञात करने का पायथन प्रोग्राम

    मान लीजिए हमारे पास एक 2D मैट्रिक्स है जो एक जंगल को दर्शाता है जहां तीन प्रकार के सेल हैं: 0 खाली सेल, 1 पेड़ सेल, 2 जलता हुआ पेड़ सेल। हर दिन, एक पेड़ आग पकड़ लेता है जब उसके आसन्न (ऊपर, नीचे, बाएं, दाएं, विकर्ण नहीं) पेड़ में आग लगी हो। हमें वह दिनों की संख्या ढूंढनी है जो हर पेड़ को जलाने में ल

  1. पायथन प्रोग्राम: संख्या के फैक्टर्स का न्यूनतम योग ढूंढें पायथन प्रोग्राम: संख्या के फैक्टर्स का न्यूनतम योग ढूंढें

    इस लेख में, हम नीचे दिए गए प्रॉब्लम स्टेटमेंट के समाधान के बारे में सीखेंगे: प्रॉब्लम स्टेटमेंट एक नंबर इनपुट दिए जाने पर, दी गई संख्या के फैक्टर्स का न्यूनतम योग ढूंढें। यहां हम सभी फैक्टर्स और उनके संबंधित योग की गणना करेंगे और फिर उनमें से न्यूनतम ढूंढेंगे। तो संख्या के गुणनफल का न्यूनतम योग ढू