Chương trình tìm chi phí tối thiểu để nhặt vàng ở hai địa điểm nhất định bằng Python

Giả sử chúng ta có một ma trận 2d và một số giá trị khác như row, col, erow0, ecol0, erow1 và ecol1. Nếu vị trí hiện tại của chúng ta là ma trận [hàng, col] và chúng ta muốn lấy vàng ở ma trận [erow0, ecol0] và ma trận [erow1, ecol1]. Chúng ta có thể đi lên, xuống, sang trái và sang phải nhưng khi chúng ta ở một ô (r, c), chúng ta phải trả ma trận chi phí [r, c], mặc dù nếu chúng ta hạ cánh tại một ô nhiều lần, chúng ta không cần phải trả chi phí cho ô đó một lần nữa. Chúng tôi phải tìm ra chi phí tối thiểu để nhặt vàng ở cả hai địa điểm.

Vì vậy, nếu đầu vào giống như

row =0, col =0, erow0 =0, ecol0 =3, erow1 =2, ecol1 =2, thì đầu ra sẽ là 8, như chúng ta đang ở (0, 0) và muốn lấy vàng từ vị trí (0, 3) và (2, 2). Vì vậy, trước tiên hãy di chuyển từ (0, 0) đến (0, 3) bằng ba bước, sau đó quay lại (0,0) rồi chuyển đến (2, 2) bằng cách đi theo 1 ô được đánh dấu.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Định nghĩa một hàm is_valid (). Điều này sẽ mất x, y

• trả về true khi x và y nằm trong phạm vi ma trận, ngược lại là false

• Định nghĩa một hàm min_cost (). Điều này sẽ mất sx, sy

• heap:=a heap với item (matrix [sx, sy], sx, sy)

• dists:=ma trận có cùng kích thước của ma trận đã cho và điền bằng inf

• dists [sx, sy]:=matrix [sx, sy]

• trong khi heap không trống, hãy thực hiện

  • (cost, x, y):=phần tử đầu tiên của heap và xóa phần tử đầu tiên khỏi heap

  • cho mỗi cặp (nx, ny) trong [(x, y - 1), (x + 1, y), (x - 1, y), (x, y + 1)], thực hiện

    • nếu is_valid (nx, ny) và ma trận [nx, ny] + cost

      • edge:=matrix [nx, ny]

      • dists [nx, ny]:=edge + cost

      • insert (edge ​​+ cost, nx, ny) vào heap

• trả lại các bản phân phối

• Từ phương thức chính, hãy làm như sau -

• res:=inf

• a:=min_cost (row, col), b:=min_cost (erow0, ecol0), c:=min_cost (erow1, ecol1)

• đối với tôi trong phạm vi 0 đến số hàng của ma trận, hãy thực hiện

  • đối với j trong phạm vi 0 đến số cột của ma trận, thực hiện

    • res:=tối thiểu của res và (a [i, j] + b [i, j] + c [i, j] - 2 * ma trận [i, j])

• trả lại res

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

import heapq
import math
class Solution:
   def solve(self, matrix, row, col, erow0, ecol0, erow1, ecol1):
      def is_valid(x, y):
         return x >= 0 and y >= 0 and x < len(matrix) and y < len(matrix[0])
      def min_cost(sx, sy):
         heap = [(matrix[sx][sy], sx, sy)]
         dists = [[math.inf] * len(matrix[0]) for _ in range(len(matrix))]
         dists[sx][sy] = matrix[sx][sy]
         while heap:
            cost, x, y = heapq.heappop(heap)
            for nx, ny in [(x, y - 1), (x + 1, y), (x - 1, y), (x, y + 1)]:
               if is_valid(nx, ny) and matrix[nx][ny] + cost < dists[nx][ny]:
                  edge = matrix[nx][ny]
                  dists[nx][ny] = edge + cost
                  heapq.heappush(heap, (edge + cost, nx, ny))
         return dists
      res = math.inf
      a, b, c = min_cost(row, col), min_cost(erow0, ecol0), min_cost(erow1, ecol1)
      for i in range(len(matrix)):
         for j in range(len(matrix[0])):
            res = min(res, a[i][j] + b[i][j] + c[i][j] - 2 * matrix[i][j])
      return res
ob = Solution()
matrix = [
   [1, 1, 1, 1, 1],
   [1, 10, 10, 10, 10],
   [1, 1, 1, 10, 10]
]
row = 0
col = 0
erow0 = 0
ecol0 = 3
erow1 = 2
ecol1 = 2
print(ob.solve(matrix, row, col, erow0, ecol0, erow1, ecol1))

Đầu vào

[ [1, 1, 1, 1, 1], [1, 10, 10, 10, 10], [1, 1, 1, 10, 10]
], 0, 0, 0, 3, 2, 2

Đầu ra

8