คำนวณระยะทางแมนฮัตตันเยี่ยมบล็อกเมืองใน Python

ภาพรวม

โจทย์คำนวณระยะทางแมนฮัตตัน (Manhattan distance) รวมในการเดินทางเยี่ยมบล็อกต่างๆ ในเมือง ตามลำดับที่กำหนด เริ่มจากตำแหน่ง (0,0) = 'start'

ตัวอย่าง

มาทริกซ์เมือง:

[["q","b","c"],
 ["d","e","z"],
 ["g","h","i"]]

บล็อกที่ต้องเยี่ยม: ["h", "b", "c"]

พิกัด:

• start: (0,0)
• h: (2,1)
• b: (0,1)
• c: (0,2)

ระยะทาง:

• start→h: |2-0|+|1-0| = 3
• h→b: |0-2|+|1-1| = 2
• b→c: |0-0|+|2-1| = 1
• รวม = 6

โค้ด Python

class Solution:
    def solve(self, mat, blocks):
        coords = {'start': (0,0)}
        for row in range(len(mat)):
            for col in range(len(mat[row])):
                coords[mat[row][col]] = (row, col)
        dist = 0
        blocks = ['start'] + blocks
        for i in range(len(blocks)-1):
            c1 = coords[blocks[i]]
            c2 = coords[blocks[i+1]]
            d = abs(c1[0]-c2[0]) + abs(c1[1]-c2[1])
            dist += d
        return dist

ob = Solution()
inp = [["q","b","c"], ["d","e","z"], ["g","h","i"]]
blk = ["h","b","c"]
print(ob.solve(inp, blk))

หลักการ Manhattan Distance

ระยะทางระหว่าง (x1,y1) และ (x2,y2) = |x1-x2| + |y1-y2|

เหมาะกับการเคลื่อนที่ในกริด (ขึ้น/ลง/ซ้าย/ขวา)

ผลลัพธ์

6