পাইথনে জল থেকে দীর্ঘতম দূরত্বের জমি খুঁজে বের করার প্রোগ্রাম

ধরুন আমাদের একটি বাইনারি ম্যাট্রিক্স আছে যেখানে, 0 জলের প্রতিনিধিত্ব করে এবং 1 ভূমিকে প্রতিনিধিত্ব করে। এখন আমাদের সেই ভূমি খুঁজে বের করতে হবে যেখানে পানি থেকে ম্যানহাটনের দীর্ঘতম দূরত্ব রয়েছে এবং অবশেষে দূরত্ব ফিরিয়ে আনতে হবে।

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

1	1	1	1
1	1	0	1
1	1	1	1
0	0	1	1

তাহলে আউটপুট হবে 3, কারণ [0,0] সেলের পানি থেকে ম্যানহাটনের দূরত্ব 3।

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

যদি A খালি হয়, তাহলে
- রিটার্ন 0
R :=ম্যাট্রিক্সের সারি গণনা, C :=ম্যাট্রিক্সের কলাম সংখ্যা
দূরত্ব :=ক্রম R x C এর একটি ম্যাট্রিক্স এবং 0 দিয়ে পূরণ করুন
q :=কিছু জোড়া (r, c) সহ একটি ডবল শেষ সারি যেখানে r এবং c ম্যাট্রিক্সের সারি এবং কলাম সূচক যেখানে ম্যাট্রিক্স[r, c] 0
যদি q এর আকার 0 বা R * C শুকিয়ে যায়, তাহলে
- রিটার্ন -1
যখন q খালি নয়, কর
- (r, c) :=q এর বাম উপাদান, তারপর q থেকে সরান
- প্রতি জোড়ার জন্য (x, y) [(r - 1, c) ,(r + 1, c) ,(r, c + 1) ,(r, c - 1) ], do
  - যদি x এবং y ম্যাট্রিক্সের পরিসরে এবং A[x, y] 1 হয়, তাহলে
    - A[x, y] :=0
    - দূরত্ব[x, y] :=দূরত্ব[r, c] + 1
    - q এর শেষে (x, y) ঢোকান
res :=প্রতিটি সারির সর্বাধিক উপাদান ধারণকারী একটি তালিকা
সর্বোচ্চ রেজোলিউশন ফেরত দিন

উদাহরণ (পাইথন)

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

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]
]