Pythonで街区を訪問する総距離

街区を表す一意の文字列のマトリックスと、訪問するブロックを含む文字列の別のリストがあるとします。ブロック行列[0][0]にいる場合は、すべてのブロックを順番に訪問するために必要なマンハッタン距離の合計を見つけます。

したがって、入力が次のような場合

ブロック=[H、B、C]

次に、「h」は2ブロック下（南）、1ブロック右（東）、「b」は2ブロック上（北）、「c」は1ブロック右（東）であるため、出力は6になります。

これを解決するには、次の手順に従います-

• coords：=キー「start」と値（0、0）のマップ
• マットの各列について、
  • マットの各列について、
    • （row、col）をcoords [mat [row、col]]に挿入します
• dist：=0
• 先頭に「start」を追加してブロックを更新します
• 範囲0からブロック-1のサイズのiの場合、実行
  • c1：=coords [blocks [i]]
  • c2：=coords [blocks [i + 1]]
  • d：=| c1 [0] -c2 [0] | + | c1 [1] -c2 [1] |
  • dist：=dist + d
• return dist

理解を深めるために、次の実装を見てみましょう-

例

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