ম্যাট্রিক্স তৈরি করার প্রোগ্রাম যেখানে প্রতিটি সেল পাইথনের নিকটতম 0 থেকে ম্যানহাটনের দূরত্ব ধরে রাখে

ধরুন আমাদের একটি বাইনারি ম্যাট্রিক্স আছে। আমাদের একই ম্যাট্রিক্স খুঁজে বের করতে হবে, কিন্তু প্রতিটি কক্ষের মান হবে ম্যানহাটান দূরত্ব নিকটতম 0। আমরা ধরে নিতে পারি ম্যাট্রিক্সে অন্তত একটি 0 বিদ্যমান।

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

তাহলে আউটপুট হবে

যেহেতু শুধুমাত্র নীচের বাম কক্ষের দূরত্ব 2 থেকে নিকটতম 0।

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

• m :=ম্যাট্রিক্সের সারির আকার, n :=ম্যাট্রিক্সের কলামের আকার
• 0 থেকে m পরিসরে y এর জন্য, করুন
  • 0 থেকে n রেঞ্জের x এর জন্য, করুন
    • যদি ম্যাট্রিক্স[y, x] অ-শূন্য হয়, তাহলে
      • ম্যাট্রিক্স[y, x] :=ইনফিনিটি
• 0 থেকে m পরিসরে y এর জন্য, করুন
  • 0 থেকে n রেঞ্জের x এর জন্য, করুন
    • যদি y অ-শূন্য হয়, তাহলে
      • ম্যাট্রিক্স[y, x] =ন্যূনতম ম্যাট্রিক্স[y, x] এবং ম্যাট্রিক্স[y - 1, x] + 1
    • যদি x অ-শূন্য হয়, তাহলে
      • ম্যাট্রিক্স[y, x] =সর্বনিম্ন ম্যাট্রিক্স[y, x] এবং ম্যাট্রিক্স[y, x - 1] + 1
• m - 1 থেকে 0 পরিসরে y-এর জন্য, 1 দ্বারা হ্রাস করুন, করুন
  n - 1 থেকে 0 রেঞ্জের x-এর জন্য
  • , 1 কমিয়ে
    করুন
    • যদি y + 1
    • ম্যাট্রিক্স[y, x] =ন্যূনতম ম্যাট্রিক্স[y, x] এবং ম্যাট্রিক্স[y + 1, x] + 1
  • যদি x + 1
  • ম্যাট্রিক্স[y, x] =সর্বনিম্ন ম্যাট্রিক্স[y, x] এবং ম্যাট্রিক্স[y, x + 1] + 1

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

উদাহরণ

import math
class Solution:
   def solve(self, matrix):
      m, n = len(matrix), len(matrix[0])
      for y in range(m):
         for x in range(n):
            if matrix[y][x]:
               matrix[y][x] = math.inf
      for y in range(m):
         for x in range(n):
            if y:
               matrix[y][x] = min(matrix[y][x], matrix[y - 1][x] + 1)
            if x:
               matrix[y][x] = min(matrix[y][x], matrix[y][x - 1] + 1)
      for y in range(m - 1, -1, -1):
         for x in range(n - 1, -1, -1):
            if y + 1 < m:
               matrix[y][x] = min(matrix[y][x], matrix[y + 1][x] + 1)
            if x + 1 < n:
               matrix[y][x] = min(matrix[y][x], matrix[y][x + 1] + 1)
      return matrix
ob = Solution()
matrix = [ [1, 0, 1], [1, 0, 1], [1, 1, 0] ]
print(ob.solve(matrix))

ইনপুট

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

আউটপুট

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