City Blocks
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
wheren
andm
are the number of rows and columns inmatrix
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 and1
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:]) | |
] | |
) |
Leave a comment