ধরুন আমাদের একটি বাইনারি ম্যাট্রিক্স আছে। আমাদের একই ম্যাট্রিক্স খুঁজে বের করতে হবে, কিন্তু প্রতিটি কক্ষের মান হবে ম্যানহাটান দূরত্ব নিকটতম 0। আমরা ধরে নিতে পারি ম্যাট্রিক্সে অন্তত একটি 0 বিদ্যমান।
সুতরাং, যদি ইনপুট মত হয়
1 | 0 | 1 |
1 | 0 | 1 |
1 | 1 | 0 |
তাহলে আউটপুট হবে
1 | 0 | 1 |
1 | 0 | 1 |
2 | 1 | 0 |
যেহেতু শুধুমাত্র নীচের বাম কক্ষের দূরত্ব 2 থেকে নিকটতম 0।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- m :=ম্যাট্রিক্সের সারির আকার, n :=ম্যাট্রিক্সের কলামের আকার
- 0 থেকে m পরিসরে y এর জন্য, করুন
- 0 থেকে n রেঞ্জের x এর জন্য, করুন
- যদি ম্যাট্রিক্স[y, x] অ-শূন্য হয়, তাহলে
- ম্যাট্রিক্স[y, x] :=ইনফিনিটি
- যদি ম্যাট্রিক্স[y, x] অ-শূন্য হয়, তাহলে
- 0 থেকে n রেঞ্জের 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
- যদি y অ-শূন্য হয়, তাহলে
- 0 থেকে n রেঞ্জের x এর জন্য, করুন
- m - 1 থেকে 0 পরিসরে y-এর জন্য, 1 দ্বারা হ্রাস করুন, করুন
- n - 1 থেকে 0 রেঞ্জের x-এর জন্য
- , 1 কমিয়ে
- করুন
- যদি y + 1
- ম্যাট্রিক্স[y, x] =ন্যূনতম ম্যাট্রিক্স[y, x] এবং ম্যাট্রিক্স[y + 1, x] + 1
- যদি y + 1
- যদি x + 1
- ম্যাট্রিক্স[y, x] =সর্বনিম্ন ম্যাট্রিক্স[y, x] এবং ম্যাট্রিক্স[y, x + 1] + 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]]