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

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


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

उदाहरण के लिए, यदि इनपुट इस तरह है:

1
2
1
1
0
1
1
1
1

तो आउटपुट 4 होगा।

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

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

  • ans := 0
  • twos := एक नई सूची
  • i को 0 से मैट्रिक्स की पंक्ति संख्या तक के लिए, करें
    • j को 0 से मैट्रिक्स की स्तंभ संख्या तक के लिए, करें
      • यदि matrix[i, j] 2 के समान है, तो
        • जोड़ी (i, j) को twos के अंत में डालें
      • जब तक twos खाली नहीं है, करें
        • temp := एक नई सूची
        • प्रत्येक जोड़ी (i, j) के लिए twos में, करें
          • प्रत्येक जोड़ी (x, y) के लिए [(i + 1, j), (i, j + 1), (i - 1, j), (i, j - 1)] में, करें
            • यदि x और y मैट्रिक्स की सीमा में हैं और matrix[x, y] 1 है, तो
              • जोड़ी (x, y) को temp के अंत में डालें
        • प्रत्येक जोड़ी (i, j) के लिए temp में, करें
          • matrix[i, j] := 2
        • twos := temp
        • ans := ans + (1 यदि twos खाली नहीं है अन्यथा 0)
  • ones = मैट्रिक्स में 1 की गिनती
  • ans लौटाएं यदि ones 0 है अन्यथा -1

बेहतर समझ के लिए निम्न कार्यान्वयन देखें:

उदाहरण

class Solution:
    def solve(self, matrix):
        ans = 0
        twos = []
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                if matrix[i][j] == 2:
                    twos.append((i, j))
        while twos:
            temp = []
            for i, j in twos:
                for x, y in [(i + 1, j), (i, j + 1), (i - 1, j), (i, j - 1)]:
                    if 0 <= x < len(matrix) and 0 <= y < len(matrix[0]) and matrix[x][y] == 1:
                        temp.append((x, y))
            for i, j in temp:
                matrix[i][j] = 2
            twos = temp
            ans += 1 if twos else 0
        ones = sum(int(matrix[i][j] == 1) for i in range(len(matrix)) for j in range(len(matrix[0])))
        return ans if ones == 0 else -1

ob = Solution()
matrix = [
    [1, 2, 1],
    [1, 0, 1],
    [1, 1, 1]
]
print(ob.solve(matrix))

इनपुट

matrix = [
    [1, 2, 1],
    [1, 0, 1],
    [1, 1, 1]
]

आउटपुट

4

  1. Python से DAG में सभी नोड्स तक पहुंचने के लिए मिनिमम वर्टेक्स कैसे ढूंढें? Python से DAG में सभी नोड्स तक पहुंचने के लिए मिनिमम वर्टेक्स कैसे ढूंढें?

    डायरेक्टेड एसाइक्लिक ग्राफ (DAG) में जिन वर्टेक्सेज़ का इन-डिग्री 0 है, उनसे सभी नोड्स पहुंचे जा सकते हैं। एल्गोरिदम सभी नोड्स का सेट बनाएं (0 से n-1)। सभी एजेज़ के डेस्टिनेशन नोड्स (v) का सेट बनाएं। सोर्स नोड्स = सभी नोड्स - डेस्टिनेशन नोड्स (यानी इन-डिग्री 0 वाले)। यही मिनिमम वर्टेक्स सेट है। उद

  1. - पायथन में दी गई संख्या के सभी अंकों का योग खोजने का प्रोग्राम

    मान लीजिए हमारे पास एक संख्या num है, हमें इसके अंकों का योग ढूंढना है। हमें इसे स्ट्रिंग्स का उपयोग किए बिना हल करना है। उदाहरण के लिए, यदि इनपुट है num = 512, तो आउटपुट होगा 8, क्योंकि 8 = 5 + 1 + 2। हल करने के चरण sum := 0 जब तक num != 0: sum := sum + (num % 10) num := num // 10 sum लौटाएं।

  1. - पायथन प्रोग्राम: लिस्ट में सबसे बड़ी संख्या ढूंढें

    इस लेख में, हम दिए गए प्रॉब्लम स्टेटमेंट को हल करने के समाधान और दृष्टिकोण के बारे में सीखेंगे। प्रॉब्लम स्टेटमेंट लिस्ट इनपुट दिए जाने पर, हमें दी गई लिस्ट में सबसे बड़ी संख्या ढूंढने की आवश्यकता है। यहां हम दो दृष्टिकोणों पर चर्चा करेंगे: सॉर्टिंग तकनीकों का उपयोग करना बिल्ट-इन max() फंक्शन का