Tổng khoảng cách để tham quan các khối thành phố bằng Python

Giả sử chúng ta có một ma trận gồm các chuỗi duy nhất đại diện cho các khối thành phố và một danh sách các chuỗi khác chứa các khối để truy cập. Nếu chúng ta đang ở ma trận khối [0] [0], thì hãy tìm tổng Manhattandistance cần thiết để truy cập mọi khối theo thứ tự.

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

Khối =[H, B, C]

Sau đó, kết quả đầu ra sẽ là 6 vì "h" là 2 khối dưới cùng (phía nam) và 1 khối bên phải (phía đông), "b" là 2 khối phía trên (phía bắc), "c" là 1 khối bên phải (phía đông).

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

• coords:=một bản đồ có khóa 'bắt đầu' và giá trị (0, 0)
• đối với mỗi hàng trong thảm, thực hiện
  • đối với mỗi col trong thảm, thực hiện
    • insert (row, col) vào coords [mat [row, col]]
• dist:=0
• cập nhật các khối bằng cách thêm 'start' vào đầu
• đối với tôi trong phạm vi từ 0 đến kích thước của khối -1, thực hiện
  • c1:=coords [blocks [i]]
  • c2:=coords [blocks [i + 1]]
  • d:=| c1 [0] -c2 [0] | + | c1 [1] -c2 [1] |
  • dist:=dist + d
• return dist

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

Ví dụ

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

Đầu ra

6