यह जाँचने का कार्यक्रम है कि पायथन में आग से बचने के लिए व्यक्ति ऊपर-बाएँ या नीचे की ओर सेल तक पहुँच सकता है या नहीं

मान लीजिए कि हमारे पास 2D मैट्रिक्स है जिसमें कुछ अलग-अलग मान नीचे दिए गए हैं -

• 0 खाली सेल के लिए

• 1 व्यक्ति के लिए

• 2 आग के लिए

• 3 दीवार के लिए

अब मान लीजिए कि केवल एक ही व्यक्ति है और प्रत्येक मोड़ में चारों दिशाओं (ऊपर, नीचे, बाएँ और दाएँ) में आग फैलती है, लेकिन आग दीवारों से नहीं फैल सकती। हमें यह जांचना होगा कि क्या व्यक्ति या तो ऊपर-बाएं कोने या नीचे-दाएं कोने या मैट्रिक्स में जा सकता है। हमें यह ध्यान रखना होगा कि प्रत्येक मोड़ पर व्यक्ति पहले चलता है, फिर आग फैलती है। यदि व्यक्ति आग के समान ही किसी भी लक्ष्य कक्ष में पहुंच जाए, तो वह सुरक्षित है। तो अगर व्यक्ति सेल में जाता है और फिर आग उसी बारी से उसी सेल में फैलती है, तो व्यक्ति अभी भी जीवित रहता है।

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

तो आउटपुट सही होगा, क्योंकि व्यक्ति ऊपरी बाएं कोने में जा सकता है।

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

• आर:=ए, सी की पंक्ति गणना:=ए की कॉलम गणना

• फ़ंक्शन को परिभाषित करें bfs() । यह कतार लेगा

• dist :=एक नक्शा जिसमें कतार के नोड के रूप में कुंजी होती है और सभी मान 0 होते हैं

• जबकि कतार खाली नहीं है, करें

  • नोड:=कतार का बायाँ आइटम, फिर बाएँ आइटम को हटाएँ

  • नोड के प्रत्येक पड़ोसी के लिए, करें

    • अगर नेई जिले में नहीं है, तो

      • जिला [नेई]:=जिला [नोड] + 1

      • कतार के अंत में नी डालें

• वापसी जिला

• मुख्य विधि से निम्न कार्य करें -

• fire_que :=एक डबल एंडेड कतार

• person_que :=एक डबल एंडेड कतार

• प्रत्येक पंक्ति अनुक्रमणिका r और पंक्ति A के लिए, करें

  • पंक्ति में प्रत्येक स्तंभ अनुक्रमणिका c और मान v के लिए, करें

    • अगर v 1 के समान है, तो

      • व्यक्ति_क्यू के अंत में जोड़ी (आर, सी) डालें

    • अन्यथा जब 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