পাইথনে সব গাছ জ্বলে যাওয়ার জন্য কত দিন লাগবে তা বের করার প্রোগ্রাম

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