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

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

तो, अगर इनपुट पसंद है

1	2	1
1	0	1
1	1	1

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

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

उत्तर:=0
दो:=एक नई सूची
मैं श्रेणी में 0 से मैट्रिक्स की पंक्ति गणना के लिए, करते हैं
- जे के लिए रेंज 0 से लेकर मैट्रिक्स के कॉलम काउंट तक, करें
  - यदि मैट्रिक्स [i, j] 2 के समान है, तो
    - दो के अंत में जोड़ी (i, j) डालें
  - जबकि दो खाली नहीं हैं, करें
    - अस्थायी:=एक नई सूची
    - प्रत्येक जोड़ी (i, j) के लिए दो में, करें
      - प्रत्येक जोड़ी (x, y) के लिए [(i + 1, j) ,(i, j + 1) ,(i - 1, j) ,(i, j-1)] में, do
        
        यदि x और y मैट्रिक्स की श्रेणी में हैं और मैट्रिक्स[x, y] 1 है, तो
        
        अस्थायी के अंत में जोड़ी (x, y) डालें
    - अस्थायी में प्रत्येक जोड़ी (i, j) के लिए, करें
      - मैट्रिक्स[i, j] :=2
    - दो:=अस्थायी
    - उत्तर :=उत्तर + (1 यदि दो खाली नहीं हैं अन्यथा 0)
  - ones =मैट्रिक्स में 1s की संख्या गिनें
  - वापसी उत्तर यदि वाले 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] ]