Computer >> Máy Tính >  >> Lập trình >> Python

Chương trình tìm số chiều cao tối thiểu cần tăng để đến đích bằng Python

Giả sử chúng ta có một ma trận M trong đó M [r] [c] đại diện cho chiều cao của ô đó. Nếu chúng ta hiện đang ở góc trên cùng bên trái và muốn đi đến góc dưới cùng bên phải. Chúng ta có thể di chuyển đến các ô liền kề (lên, xuống, trái, phải) chỉ khi chiều cao của ô liền kề đó nhỏ hơn hoặc bằng chiều cao của ô hiện tại. Chúng ta có thể tăng chiều cao của bất kỳ số lượng ô nào trước khi di chuyển, vì vậy chúng ta phải tìm tổng chiều cao tối thiểu cần tăng để có thể chuyển đến ô dưới cùng bên phải.

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

2 4 5
8 6 1

thì đầu ra sẽ là 4, vì chúng ta có thể đi theo đường dẫn sau [2, 4, 5, 1] ​​và thay đổi độ cao thành cấu hình này -

5 5 5
8 6 1

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

INF:=infinity

  • R, C:=số hàng của ma trận, số cột của ma trận

  • pq:=tạo hàng đợi ưu tiên bằng cách sử dụng heap và chèn [0, R-1, C-1, M [-1, -1]] vào đó

  • dist:=một bản đồ

  • dist [R-1, C-1, A [-1, -1]]:=0

  • trong khi pq không trống, thực hiện

    • xóa một phần tử khỏi pq và lưu trữ chúng thành d, r, c, h

    • nếu dist [r, c, h]

      • chuyển sang lần lặp tiếp theo

    • nếu r và c đều là 0 thì

      • trở lại d

    • cho mỗi cặp (nr, nc) trong [[r + 1, c], [r, c + 1], [r-1, c], [r, c-1]], thực hiện

      • nếu 0 <=nr

        • nếu d2

          • dist [nr, nc, h2]:=d2

          • chèn [d2, nr, nc, h2] vào pq

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

Ví dụ 

import collections
import heapq
class Solution:
   def solve(self, A):
      INF = float('inf')
      R, C = len(A), len(A[0])

      pq = [[0, R-1, C-1, A[-1][-1]]]
      dist = collections.defaultdict(lambda: INF)
      dist[R-1, C-1, A[-1][-1]] = 0
      while pq:
         d, r, c, h = heapq.heappop(pq)
         if dist[r, c, h] < d:
            continue
         if r == c == 0:
            return d
         for nr, nc in [[r+1, c], [r, c+1], [r-1, c], [r, c-1]]:
            if 0 <= nr < R and 0 <= nc < C:
               h2 = max(A[nr][nc], h)
               d2 = d + max(h2 - A[nr][nc], 0)
               if d2 < dist[nr, nc, h2]:
                  dist[nr, nc, h2] = d2
                  heapq.heappush(pq, [d2, nr, nc, h2])
ob = Solution()
matrix = [
[2, 4, 5],
[8, 6, 1]
]
print(ob.solve(matrix))

Đầu vào 

[[2, 4, 5],[8, 6, 1]]

Đầu ra 

4