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

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

0 खाली सेल के लिए
1 व्यक्ति के लिए
2 आग के लिए
3 दीवार के लिए

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

इसलिए, यदि इनपुट इस प्रकार है:

0	0	0
0	0	1
0	0	2

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

हल करने के चरण

R := A की पंक्तियों की संख्या, C := A के स्तंभों की संख्या
bfs() फ़ंक्शन परिभाषित करें। यह queue लेगा
- dist := एक मैप जिसमें queue के नोड कुंजी के रूप में हैं और सभी मान 0 हैं
- जब तक queue खाली नहीं है, करें
  - node := queue का बायां आइटम, फिर बायां आइटम हटाएं
  - node के प्रत्येक पड़ोसी nei के लिए, करें
    - यदि nei, dist में नहीं है, तो
      - dist[nei] := dist[node] + 1
      - nei को queue के अंत में डालें
- dist लौटाएं

मुख्य विधि से निम्नलिखित करें:

fire_que := एक डबल एंडेड क्यू
person_que := एक डबल एंडेड क्यू
प्रत्येक पंक्ति इंडेक्स r और पंक्ति A के लिए, करें
- प्रत्येक स्तंभ इंडेक्स c और मान v के लिए पंक्ति में, करें
  - यदि v, 1 के समान है, तो (r, c) को person_que के अंत में डालें
  - अन्यथा जब v, 2 के समान है, तो (r, c) को fire_que के अंत में डालें
dist_fire := bfs(fire_que)
dist_person := bfs(person_que)
प्रत्येक place के लिए (0, 0), (R - 1, C - 1) में, करें
- यदि (dist_fire[place] यदि मौजूद नहीं तो INF) >= (dist_person[place] यदि मौजूद नहीं तो 2 * INF), तो True लौटाएं
False लौटाएं

उदाहरण

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