ব্যক্তি পরীক্ষা করার জন্য প্রোগ্রামটি পাইথনে আগুন এড়িয়ে উপরে-বাম বা নীচের ডানদিকের ঘরে পৌঁছাতে পারে

ধরুন আমাদের কাছে একটি 2D ম্যাট্রিক্স আছে যার নিচের মত কয়েকটি ভিন্ন মান রয়েছে −

• খালি কক্ষের জন্য 0

• একজন ব্যক্তির জন্য 1

• আগুনের জন্য 2

• একটি দেয়ালের জন্য 3

এখন অনুমান করুন শুধুমাত্র একজন ব্যক্তি আছে এবং প্রতিটি পালা করে আগুন চার দিকে (উপর, নিচে, বাম এবং ডানে) প্রসারিত হয় কিন্তু আগুন দেয়াল দিয়ে প্রসারিত হতে পারে না। আমাদের পরীক্ষা করতে হবে যে ব্যক্তিটি উপরের-বাম কোণে বা নীচে-ডান কোণে বা ম্যাট্রিক্সে যেতে পারে কিনা। আমাদের মনে রাখতে হবে যে প্রতিটি পাল্লায়, ব্যক্তি প্রথমে নড়াচড়া করে, তারপর আগুন প্রসারিত হয়। যদি ব্যক্তি আগুনের মতো একই সময়ে লক্ষ্যবস্তু কোষগুলির মধ্যে এটি তৈরি করে তবে সে নিরাপদ। তাই যদি ব্যক্তি কোষে যায় এবং তারপর আগুন একই পালাক্রমে একই কোষে প্রসারিত হয়, তবে ব্যক্তিটি এখনও বেঁচে থাকে।

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

তাহলে আউটপুট হবে True, যেহেতু ব্যক্তি উপরের বাম কোণে যেতে পারে।

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

• R :=A এর সারি গণনা, C :=A এর কলাম গণনা

• একটি ফাংশন bfs() সংজ্ঞায়িত করুন। এটি সারি লাগবে

• dist :=একটি মানচিত্র যেখানে সারির নোড হিসাবে কী রয়েছে এবং সমস্ত মান 0

• সারি খালি না থাকার সময়, করুন

  • নোড :=সারির বাম আইটেম, তারপর বাম আইটেম মুছুন

  • নোডের প্রতিটি প্রতিবেশীর জন্য, করুন

    • যদি nei জেলায় না থাকে, তাহলে

      • dist[nei] :=dist[node] + 1

      • সারির শেষে nei ঢোকান

• প্রত্যাবর্তন জেলা

• প্রধান পদ্ধতি থেকে নিম্নলিখিতগুলি করুন -

• fire_que :=একটি ডবল শেষ সারি

• person_que :=একটি ডবল শেষ সারি

• প্রতিটি সারি সূচী r এবং সারি A এর জন্য, করুন

  • প্রতিটি কলামের জন্য সূচী c এবং সারিতে v মান, করুন

    • যদি v 1 এর মত হয়, তাহলে

      • person_que

        এর শেষে জোড়া (r, c) সন্নিবেশ করুন

    • অন্যথায় যখন v 2 এর মত হয়, তখন

      • Fire_que

        এর শেষে জোড়া (r, c) সন্নিবেশ করুন

      • dist_fire :=bfs(fire_que)

• dist_person :=bfs(person_que)

• প্রতিটি স্থানের জন্য (0, 0), (R − 1, C − 1), do

  • যদি (dist_fire[place] যদি না থাকে তাহলে INF)>=(dist_person[place] যদি না থাকে তাহলে, 2 * INF), তারপর

    • রিটার্ন ট্রু

• রিটার্ন ফলস

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

উদাহরণ

from collections import deque
class Solution:
   def solve(self, A):
      INF = int(1e9)
      R, C = len(A), len(A[0])
      def get_nei(r, c):
         for nr, nc in [[r − 1, c], [r, c − 1], [r + 1, c], [r, c + 1]]:
            if 0 <= nr < R and 0 <= nc < C and A[nr][nc] != 3:
               yield nr, nc
         def bfs(queue):
            dist = {node: 0 for node in queue}
            while queue:
               node = queue.popleft()
               for nei in get_nei(*node):
                  if nei not in dist:
                     dist[nei] = dist[node] + 1
                     queue.append(nei)
            return dist
         fire_que = deque()
         person_que = deque()
         for r, row in enumerate(A):
            for c, v in enumerate(row):
               if v == 1:
                  person_que.append((r, c))
               elif v == 2:
                  fire_que.append((r, c))
         dist_fire = bfs(fire_que)
         dist_person = bfs(person_que)
         for place in ((0, 0), (R− 1, C− 1)):
            if dist_fire.get(place, INF) >= dist_person.get(place, 2 * INF):
               return True
         return False
ob = Solution()
matrix = [
   [0, 0, 0],
   [0, 0, 1],
   [0, 0, 2]
]
print(ob.solve(matrix))

ইনপুট

[ [0, 0, 0], [0, 0, 1], [0, 0, 2] ]

আউটপুট

True