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

สมมติว่าเรามีเมทริกซ์ไบนารี เราต้องหาเมทริกซ์เดียวกัน แต่ค่าของแต่ละเซลล์จะเท่ากับระยะทางแมนฮัตตันจาก 0 ที่ใกล้ที่สุด เราสามารถสมมติได้ว่าเมทริกซ์มี 0 อย่างน้อยหนึ่งตัว

ดังนั้นหากอินพุตเป็นแบบ

แล้วผลลัพธ์ที่ได้จะเป็น

เนื่องจากมีเพียงเซลล์ด้านล่างซ้ายเท่านั้นที่มีระยะห่าง 2 ถึง 0 ที่ใกล้ที่สุด

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• m :=ขนาดแถวของเมทริกซ์ n :=ขนาดคอลัมน์ของเมทริกซ์
• สำหรับ y ในช่วง 0 ถึง m ให้ทำ
  • สำหรับ x ในช่วง 0 ถึง n ให้ทำ
    • ถ้าเมทริกซ์[y, x] ไม่ใช่ศูนย์ ดังนั้น
      • เมทริกซ์[y, x] :=อินฟินิตี้
• สำหรับ y ในช่วง 0 ถึง m ให้ทำ
  • สำหรับ x ในช่วง 0 ถึง n ให้ทำ
    • ถ้า y ไม่ใช่ศูนย์ แล้ว
      • เมทริกซ์[y, x] =ขั้นต่ำของเมทริกซ์[y, x] และเมทริกซ์[y - 1, x] + 1
    • ถ้า x ไม่ใช่ศูนย์ แล้ว
      • เมทริกซ์[y, x] =ขั้นต่ำของเมทริกซ์[y, x] และเมทริกซ์[y, x - 1] + 1
• สำหรับ y ในช่วง m - 1 ถึง 0, ลดลง 1 ทำ
  • สำหรับ x ในช่วง n - 1 ถึง 0, ลดลง 1, ทำ
    • ถ้า y + 1
    • เมทริกซ์[y, x] =ขั้นต่ำของเมทริกซ์[y, x] และเมทริกซ์[y + 1, x] + 1
  • ถ้า x + 1
  • เมทริกซ์[y, x] =ขั้นต่ำของเมทริกซ์[y, x] และเมทริกซ์[y, x + 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]]