Chương trình tìm số coin mà chúng ta có thể chọn từ ô trên cùng xuống ô dưới cùng bên phải và trả lại bằng Python

Giả sử chúng ta có một ma trận 2D với 3 giá trị khả dĩ -

• 0 cho một ô trống.

• 1 cho một đồng xu.

• −1 cho một bức tường.

Chúng ta phải tìm số xu tối đa mà chúng ta có thể lấy bằng cách bắt đầu từ ô trên cùng bên trái và đến ô dưới cùng bên phải bằng cách chỉ di chuyển theo hướng sang phải hoặc hướng xuống. Sau đó, quay lại ô trên cùng bên trái bằng cách chỉ di chuyển lên hoặc sang trái. Khi chúng ta nhặt một đồng xu, giá trị ô sẽ trở thành 0. Nếu chúng ta không thể đến ô dưới cùng bên phải, thì trả về 0.

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

thì đầu ra sẽ là 8.

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

• n:=số hàng của tấm lót, m:=số cột của tấm lót

• Định nghĩa một hàm dùng (). Điều này sẽ lấy i, j, k, l

• nếu tôi và j không thuộc phạm vi mat hoặc mat [i, j] giống −1, thì

  • return −inf

• nếu k và l không thuộc phạm vi mat hoặc mat [k, l] giống −1 thì

  • return −inf

• nếu i, j, k và l đều bằng 0 thì

  • chiếu trở lại [0, 0]

• tốt nhất:=−inf

• cho mỗi cặp (dx1, dy1) trong [(−1, 0), (0, −1)], thực hiện

  • đối với mỗi cặp (dx2, dy2) trong [(−1, 0), (0, −1)], thực hiện

    • tốt nhất:=tối đa trong tổng số tốt nhất và sử dụng (i + dy1, j + dx1, k + dy2, l + dx2)

• return mat [i, j] + (1 khi tôi không giống k, nếu không thì 0) * mat [k, l] + best

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

• trả về tối đa là 0 và dùng (n - 1, m - 1, n - 1, m - 1)

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

Ví dụ

class Solution:
   def solve(self, mat):
      n, m = len(mat), len(mat[0])
      def util(i, j, k, l):
         if not (0 <= i < n and 0 <= j < m) or mat[i][j] == −1:
            return −1e9
         if not (0 <= k < n and 0 <= l < m) or mat[k][l] == −1:
            return −1e9
         if i == 0 and j == 0 and k == 0 and l == 0:
            return mat[0][0]
         best = −1e9
         for dx1, dy1 in [(−1, 0), (0, −1)]:
            for dx2, dy2 in [(−1, 0), (0, −1)]:
               best = max(best, util(i + dy1, j + dx1, k + dy2, l + dx2))
         return mat[i][j] + (i != k) * mat[k][l] + best
      return max(0, util(n − 1, m − 1, n − 1, m − 1))
ob = Solution()
matrix = [
   [0, 1, 1],
   [1, 1, 1],
   [1, −1, 1],
   [0, 1, 1]
]
print(ob.solve(matrix))

Đầu vào

[
   [0, 1, 1],
   [1, 1, 1],
   [1, −1, 1],
   [0, 1, 1]
]

Đầu ra

8