समस्या विवरण
यूनिक स्ट्रिंग्स की एक मैट्रिक्स (सिटी ब्लॉक्स) और विजिट करने वाले ब्लॉक्स की सूची दी गई है। matrix[0][0] से शुरू करके, क्रम से प्रत्येक ब्लॉक तक जाने के लिए आवश्यक कुल मैनहट्टन दूरी ज्ञात करें।
उदाहरण
मैट्रिक्स:
| q | b | c |
| d | e | z |
| g | h | i |
ब्लॉक्स: ["h", "b", "c"]
आउटपुट: 6
एल्गोरिदम
- प्रत्येक ब्लॉक के निर्देशांक
coordsमैप में स्टोर करें blocksकी शुरुआत में'start'(0,0) जोड़ें- क्रमागत ब्लॉक्स के बीच मैनहट्टन दूरी जोड़ें:
|r1-r2| + |c1-c2| - कुल दूरी वापस करें
पायथन कार्यान्वयन
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"]], ["h", "b", "c"]
आउटपुट
6
