একটি ২D ম্যাট্রিক্স দেওয়া আছে: ০ = খালি, ১ = ব্যক্তি, ২ = আগুন, ৩ = দেওয়াল। প্রতিটি টার্নে আগুন চারদিকে ছড়ায় (দেওয়াল বাধা দেয়)। ব্যক্তি প্রথমে মুভ করে, তারপর আগুন ছড়ায়। ব্যক্তি উপরের বাম (0,0) বা নিচের ডান (R-1,C-1) কোণে পৌঁছাতে পারে কিনা চেক করতে হবে। একই সময়ে আগুন পৌঁছালেও ব্যক্তি সেফ মाना হবে।
উদাহরণ: ম্যাট্রিক্স [[0,0,0],[0,0,1],[0,0,2]] → আউটপুট True।
সমাধানের ধাপসমূহ (BFS - Multi-source)
R, C := সারি ও কলাম।
bfs(queue)ফাংশন: মাল্টি-সোর্স BFS চালিয়ে প্রতিটি সেল পর্যন্ত দূরত্ব (Dist) ম্যাপ রিটার্ন করে।আগুনের সকল সোর্স দিয়ে
dist_fireবের করুন।ব্যক্তির সোর্স দিয়ে
dist_personবের করুন।দুটি টার্গেট (0,0) এবং (R-1,C-1) এর জন্য চেক করুন:
dist_fire[place] >= dist_person[place]হলে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
