অজগরে সব গাছ পোড়াতে কত দিন লাগবে তা বের করার কর্মসূচি

ধরুন আমাদের একটি 2D ম্যাট্রিক্স একটি বনকে প্রতিনিধিত্ব করে যেখানে তিন ধরনের কোষ রয়েছে:0 খালি সেল 1 ট্রি সেল 2 ট্রি ফায়ার সেলের উপর প্রতিদিন, একটি গাছে আগুন ধরে যখন একটি সংলগ্ন (উপরে, নীচে, বাম, ডান, নয়) তির্যক) গাছে আগুন লেগেছে। প্রতিটি গাছে আগুন ধরতে কত দিন লাগবে তা আমাদের খুঁজে বের করতে হবে। যদি তা সম্ভব না হয় -1 রিটার্ন করুন।

সুতরাং, যদি ইনপুট মত হয়

1	2	1
1	0	1
1	1	1

তাহলে আউটপুট হবে 4,

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

উত্তর :=0
দুই :=একটি নতুন তালিকা
আমি 0 থেকে ম্যাট্রিক্সের সারি গণনার পরিসরের জন্য, কর
- ম্যাট্রিক্সের 0 থেকে কলাম গণনা পরিসরে j-এর জন্য
  - যদি ম্যাট্রিক্স[i, j] 2 এর মত হয়, তাহলে
    - দুইয়ের শেষে জোড়া (i, j) ঢোকান
  - যদি দুইটি খালি না থাকে, তখন কর
    - temp :=একটি নতুন তালিকা
    - প্রতি জোড়ার জন্য (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) temp, do
      - ম্যাট্রিক্স[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] ]