পাইথনে বাইনারি ম্যাট্রিক্সে জল থেকে সর্বোচ্চ ম্যানহ্যাটান দূরত্বের জমি খুঁজে বের করার প্রোগ্রাম

একটি বাইনারি ম্যাট্রিক্স দেওয়া আছে (০ = জল, ১ = জমি)। এমন জমি খুঁজে বের করতে হবে যেটির জল থেকে ম্যানহ্যাটান দূরত্ব সর্বোচ্চ। সেই দূরত্ব রিটার্ন করুন।

উদাহরণস্বরূপ,

matrix = [
  [1,1,1,1],
  [1,1,0,1],
  [1,1,1,1],
  [0,0,1,1]
]

আউটপুট ৩, কারণ [0,0] সেলের জল থেকে দূরত্ব ৩।

সমাধানের পদ্ধতি (মাল্টি-সোর্স BFS)

সকল জল সেল (০) কে কিউ-এ ঢুকিয়ে দিন (মাল্টি-সোর্স BFS)।
distance ম্যাট্রিক্স ইনিশিয়ালাইজ করুন।
BFS চলাকালীন প্রতিটি জমি সেল (১) এর জন্য distance = parent_distance + 1 আপডেট করুন এবং কিউ-এ ঢুকান।
শেষে distance ম্যাট্রিক্সের সর্বোচ্চ মান রিটার্ন করুন।

পাইথন কোড উদাহরণ

from collections import deque

class Solution:
    def solve(self, A):
        if not A:
            return 0
        R, C = len(A), len(A[0])
        distance = [[0]*C for _ in range(R)]
        q = deque((r, c) for r in range(R) for c in range(C) if not A[r][c])
        if len(q) in (0, R*C):
            return -1
        while q:
            r, c = q.popleft()
            for x, y in [(r-1,c),(r+1,c),(r,c+1),(r,c-1)]:
                if 0 <= x < R and 0 <= y < C and A[x][y]:
                    A[x][y] = 0
                    distance[x][y] = distance[r][c] + 1
                    q.append((x, y))
        return max(max(row) for row in distance)

ob = Solution()
matrix = [[1,1,1,1],[1,1,0,1],[1,1,1,1],[0,0,1,1]]
print(ob.solve(matrix))

ইনপুট

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