Chương trình tạo ma trận trong đó mỗi ô giữ khoảng cách Manhattan từ 0 gần nhất bằng Python

Giả sử chúng ta có một ma trận nhị phân. Chúng ta phải tìm cùng một ma trận, nhưng giá trị của mỗi ô sẽ là khoảng cách Manhattan đến 0. Chúng ta có thể giả sử tồn tại ít nhất một số 0 trong ma trận.

Vì vậy, nếu đầu vào giống như

thì đầu ra sẽ là

vì chỉ ô dưới cùng bên trái có khoảng cách từ 2 đến 0 gần nhất.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• m:=kích thước hàng của ma trận, n:=kích thước cột của ma trận
• đối với y trong phạm vi từ 0 đến m, thực hiện
  • đối với x trong phạm vi từ 0 đến n, thực hiện
    • nếu ma trận [y, x] khác 0 thì
      • ma trận [y, x]:=infinity
• đối với y trong phạm vi từ 0 đến m, thực hiện
  • đối với x trong phạm vi từ 0 đến n, thực hiện
    • nếu y khác 0, thì
      • ma trận [y, x] =cực tiểu của ma trận [y, x] và ma trận [y - 1, x] + 1
    • nếu x khác 0, thì
      • ma trận [y, x] =cực tiểu của ma trận [y, x] và ma trận [y, x - 1] + 1
• đối với y trong phạm vi m - 1 đến 0, giảm đi 1, thực hiện
  • cho x trong phạm vi n - 1 đến 0, giảm 1, thực hiện
    • nếu y + 1
    • ma trận [y, x] =cực tiểu của ma trận [y, x] và ma trận [y + 1, x] + 1
  • nếu x + 1
  • ma trận [y, x] =cực tiểu của ma trận [y, x] và ma trận [y, x + 1] + 1

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

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