โปรแกรมสร้างเมทริกซ์ระยะแมนฮัตตันจาก 0 ใกล้ที่สุดใน Python

สมมติว่ามีเมทริกซ์ไบนารี ต้องการสร้างเมทริกซ์เดียวกันแต่แต่ละเซลล์เป็นระยะแมนฮัตตันไปยัง 0 ใกล้ที่สุด สมมติว่ามี 0 อย่างน้อย 1 ตัว

ตัวอย่าง: [[1,0,1],[1,0,1],[1,1,0]] ผลลัพธ์ [[1,0,1],[1,0,1],[2,1,0]]

ขั้นตอนการแก้ปัญหา

1. m, n = ขนาดเมทริกซ์
2. ผ่าน 2 รอบ (top-left to bottom-right):
   • ถ้าเซลล์ไม่ใช่ 0 ตั้งเป็น infinity
   • อัปเดตจากบนและซ้าย: min(ค่าปัจจุบัน, บน+1, ซ้าย+1)
3. ผ่าน 2 รอบ (bottom-right to top-left):
   • อัปเดตจากล่างและขวา: min(ค่าปัจจุบัน, ล่าง+1, ขวา+1)
4. คืนเมทริกซ์

ตัวอย่างโค้ด

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