Chương trình tạo ma trận khoảng cách Manhattan đến 0 gần nhất trong Python

Mô tả bài toán

Cho ma trận nhị phân. Tạo ma trận cùng kích thước, mỗi ô chứa khoảng cách Manhattan đến ô 0 gần nhất. Đảm bảo có ít nhất một 0.

Ví dụ: [[1,0,1],[1,0,1],[1,1,0]] → [[1,0,1],[1,0,1],[2,1,0]].

Giải thuật (Hai lần quét - Two-pass DP)

1. Khởi tạo: ô có giá trị 1 đặt thành vô cực.
2. Quét từ trên-trái sang dưới-phải: cập nhật khoảng cách từ trên và trái.
3. Quét từ dưới-phải sang trên-trái: cập nhật khoảng cách từ dưới và phải.
4. Trả về ma trận kết quả.

Ví dụ mã Python

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

Đầu vào

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

Đầu ra

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