Pythonで街区を訪問する総移動距離（マンハッタン距離）を求める方法

問題の概要

都市の街区を表す、重複のない文字列からなる行列(mat)と、訪問したい街区名のリスト(blocks)が与えられます。現在位置は mat[0][0] から出発し、リストに記載された順番どおりにすべての街区を訪問するときに必要なマンハッタン距離の合計を求めるのがこの問題の目的です。

マンハッタン距離とは、2点間の移動距離を「上下方向の差」と「左右方向の差」の絶対値の和として測るもので、碁盤の目状に区画された街路を移動するイメージに近い距離概念です。

たとえば、入力が次のような場合を考えてみましょう。

blocks = ["h", "b", "c"]

このとき出力は 6 となります。移動の内訳は以下の通りです。

• 「h」へ移動：下(南)へ2ブロック＋右(東)へ1ブロック ＝ 距離3
• 「b」へ移動：上(北)へ2ブロック ＝ 距離2
• 「c」へ移動：右(東)へ1ブロック ＝ 距離1

合計は 3 + 2 + 1 = 6 です。

解き方の手順

この問題を解くには、以下の手順に従います。

• キー 'start'、値 (0, 0) を持つマップ coords を作成する
• mat の各行・各列を走査し、coords[mat[row][col]] に座標 (row, col) を登録する
• 累積距離 dist を 0 で初期化する
• blocks の先頭に 'start' を追加する
• i を 0 から blocks のサイズ - 2 までループし、隣接する2つの街区間の距離 d = |c1[0]-c2[0]| + |c1[1]-c2[1]| を計算して dist に加算する
• 最後に 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