1 minute read

You are given a two-dimensional matrix of unique strings representing city blocks, and a list of strings blocks to visit. Given that you are sitting at block matrix[0][0], return the total Manhattan distance required to visit every block in order.

Constraints

  • 0 ≤ n * m ≤ 100,000 where n and m are the number of rows and columns in matrix

https://binarysearch.com/problems/City-Blocks

ExamplesPermalink

Example 1Permalink

Input

  • matrix =
[['a','b','c'],
 ['d','e','f'],
 ['g','h','i']]
  • blocks = ['h', 'b', 'c']

Output

  • answer = 6

Explanation

  • “h” is 2 blocks south and 1 block east.
  • “b” is 2 blocks north.
  • “c” is 1 block east.

Which adds up to 6.

SolutionPermalink

class Solution:
def solve(self, matrix, blocks):
loc = {c: (i, j) for (i, row) in enumerate(matrix) for (j, c) in enumerate(row)}
path = [(0, 0)] + [loc[b] for b in blocks]
return sum(
[
abs(x2[0] - x1[0]) + abs(x2[1] - x1[1])
for (x1, x2) in zip(path, path[1:])
]
)
view raw City-Blocks.py hosted with ❤ by GitHub

Leave a comment