পাইথনে বাইনারি ম্যাট্রিক্স থেকে প্রতিটি সেলের নিকটতম ০-এর ম্যানহ্যাটান দূরত্ব বের করার প্রোগ্রাম

মান লক্ষ্য করুন আমাদের কাছে একটি বাইনারি ম্যাট্রিক্স আছে। আমাদের কাজ হল একই ম্যাট্রিক্স রিটার্ন করা কিন্তু প্রতিটি সেলের মান হবে সেটির নিকটতম ০-এর ম্যানহ্যাটান দূরত্ব। আমরা ধরে নিতে পারি ম্যাট্রিক্সে কমপক্ষে একটি ০ আছে।

উদাহরণস্বরূপ, যদি ইনপুট হয়:

তবে আউটপুট হবে:

কারণ শুধু নিচের বাম সেলটির দূরত্ব ২ নিকটতম ০ পর্যন্ত।

• m := matrix-র সারির সংখ্যা, n := matrix[0]-র কলামের সংখ্যা
• y কে ০ থেকে m পর্যন্ত লুপ চালান:
  • x কে ০ থেকে n পর্যন্ত লুপ চালান:
    • যদি matrix[y][x] নন-জিরো হয়, তবে matrix[y][x] := infinity
• y কে ০ থেকে m পর্যন্ত লুপ চালান:
  • x কে ০ থেকে n পর্যন্ত লুপ চালান:
    • যদি y নন-জিরো হয়, তবে matrix[y][x] = min(matrix[y][x], matrix[y-1][x] + 1)
    • যদি x নন-জিরো হয়, তবে matrix[y][x] = min(matrix[y][x], matrix[y][x-1] + 1)
• y কে m-1 থেকে ০ পর্যন্ত লুপ চালান:
  • x কে n-1 থেকে ০ পর্যন্ত লুপ চালান:
    • যদি y+1 < m হয়, তবে matrix[y][x] = min(matrix[y][x], matrix[y+1][x] + 1)
    • যদি x+1 < n হয়, তবে matrix[y][x] = min(matrix[y][x], matrix[y][x+1] + 1)
• matrix রিটার্ন করুন।

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