Tổng khoảng cách Manhattan thăm khối thành phố trong Python

Cho ma trận chuỗi duy nhất đại diện các khối thành phố, và danh sách khối cần thăm. Bắt đầu tại matrix[0][0], tìm tổng khoảng cách Manhattan để thăm theo thứ tự.

Ví dụ: ma trận 3x3, khối thăm ['h','b','c'] → kết quả 6.

Các bước giải quyết

• Tạo từ điển coords ánh xạ tên khối → tọa độ (hàng, cột)
• dist = 0, thêm 'start' vào đầu danh sách khối
• Duyệt từng cặp liên tiếp: tính khoảng cách Manhattan và cộng dồn
• Trả về dist

Ví dụ mã 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))

Đầu vào

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

Đầu ra

6