ระยะทางทั้งหมดเพื่อเยี่ยมชมบล็อกเมืองใน Python

สมมติว่าเรามีเมทริกซ์ของสตริงที่ไม่ซ้ำกันซึ่งแสดงถึงบล็อกของเมือง และรายการสตริงอื่นที่มีบล็อกให้เยี่ยมชม หากเราอยู่ที่ block matrix[0][0] ให้หาระยะทางแมนฮัตตันทั้งหมดที่ต้องการเพื่อเข้าชมทุกบล็อกตามลำดับ

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

บล็อค =[H,B,C]

จากนั้นผลลัพธ์จะเป็น 6 เนื่องจาก "h" คือ 2 บล็อกด้านล่าง (ใต้) และ 1 บล็อกด้านขวา (ตะวันออก) "b" คือ 2 บล็อกขึ้นไป (เหนือ) "c" คือ 1 บล็อกด้านขวา (ตะวันออก)

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

• coords :=แผนที่ที่มีคีย์ 'start' และค่า (0, 0)
• สำหรับแต่ละแถวในเสื่อ ทำ
  • สำหรับแต่ละ col in mat ทำ
    • แทรก (row,col) ลงใน coords[mat[row, col]]
• dist :=0
• อัปเดตบล็อคโดยเพิ่ม 'start' ที่จุดเริ่มต้น
• สำหรับฉันในช่วง 0 ถึงขนาดของบล็อก -1 ทำ
  • c1 :=coords[blocks[i]]
  • c2 :=coords[blocks[i+1]]]
  • d :=|c1[0]-c2[0]| + |c1[1]-c2[1]|
  • dist :=dist + 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))

อินพุต

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

ผลลัพธ์

6