Computer >> 컴퓨터 >  >> 프로그램 작성 >> Python

Python에서 도시 블록을 방문하는 총 거리

<시간/>

도시 블록을 나타내는 고유 문자열 행렬과 방문할 블록을 포함하는 문자열의 또 다른 목록이 있다고 가정합니다. 블록 행렬[0][0]에 있는 경우 모든 블록을 순서대로 방문하는 데 필요한 총 맨해튼 거리를 찾으십시오.

따라서 입력이 다음과 같으면

Q C
Z

블록 =[H,B,C]

그러면 "h"는 2블록 아래쪽(남쪽)과 1블록 오른쪽(동쪽), "b"는 2블록 위쪽(북쪽), "c"는 1블록 오른쪽(동쪽)이므로 출력은 6이 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

  • coords :='start' 키와 값(0, 0)이 있는 지도
  • 매트의 각 행에 대해 다음을 수행합니다.
    • 매트의 각 열에 대해 다음을 수행합니다.
      • (행, 열)을 좌표[mat[row, col]]에 삽입
  • 거리:=0
  • 시작 부분에 '시작'을 추가하여 블록 업데이트
  • 0에서 블록 크기 -1 사이의 i에 대해
    • c1 :=좌표[블록[i]]
    • c2 :=좌표[블록[i+1]]
    • d :=|c1[0]-c2[0]| + |c1[1]-c2[1]|
    • dist :=dist + d
  • 반환 거리

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

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