Chương trình tìm độ dài của độ dài đường dẫn ma trận dài nhất trong Python

Giả sử chúng ta có một ma trận nhị phân, trong đó 0 biểu thị ô trống và 1 biểu thị tường. Chúng ta có thể bắt đầu ở bất kỳ ô trống nào trên hàng đầu tiên và muốn kết thúc ở bất kỳ ô trống nào trên hàng cuối cùng. Chúng ta có thể di chuyển sang trái, phải hoặc xuống, chúng ta phải tìm ra con đường dài nhất mà chúng ta có thể đến thăm từng ô nhiều nhất một lần. Nếu không được, hãy trả về 0.

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

thì đầu ra sẽ là 10, vì Chúng ta có thể di chuyển (0, 3), (0, 2), (0, 1), (0, 0), (1, 0), (1, 1), (1, 2), (2, 2), (2, 1), (2, 0).

Để 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 ma trận
• M:=số cột của ma trận
• dp:=danh sách kích thước M và điền vào -1
• đối với tôi trong phạm vi từ 0 đến N - 1, thực hiện
  • ndp:=danh sách kích thước M và điền vào -1
  • ndp2:=danh sách kích thước M và điền vào -1
  • đối với j trong phạm vi từ 0 đến M - 1, thực hiện
    • nếu ma trận [i, j] không phải là 1 và (i giống 0 hoặc dp [j]> -1), thì
      • ndp [j]:=dp [j] + 1
      • ndp2 [j]:=dp [j] + 1
  • đối với j trong phạm vi từ 1 đến M - 1, thực hiện
    • nếu ma trận [i, j] không phải là 1 và ndp [j - 1]> -1, thì
      • ndp [j]:=tối đa của ndp [j] và (ndp [j - 1] + 1)
  • cho j trong phạm vi M - 2 đến 0, giảm 1, thực hiện
    • nếu ma trận [i, j] không phải là 1 và ndp2 [j + 1]> -1, thì
      • ndp2 [j]:=tối đa của ndp2 [j] và (ndp2 [j + 1] + 1)
      • ndp [j]:=tối đa của ndp [j] và ndp2 [j]
  • dp:=ndp
• return (tối đa là dp) + 1

Ví dụ

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

def solve(matrix):
   N = len(matrix)
   M = len(matrix[0])
   dp = [-1 for i in matrix[0]]
   for i in range(N):
      ndp = [-1 for j in matrix[0]]
      ndp2 = [-1 for j in matrix[0]]
      for j in range(M):
         if matrix[i][j] != 1 and (i == 0 or dp[j] > -1):
            ndp[j] = dp[j] + 1
            ndp2[j] = dp[j] + 1

      for j in range(1, M):
         if matrix[i][j] != 1 and ndp[j - 1] > -1:
            ndp[j] = max(ndp[j], ndp[j - 1] + 1)

      for j in range(M - 2, -1, -1):
         if matrix[i][j] != 1 and ndp2[j + 1] > -1:
            ndp2[j] = max(ndp2[j], ndp2[j + 1] + 1)
            ndp[j] = max(ndp[j], ndp2[j])

      dp = ndp
   return max(dp) + 1

matrix = [
[0, 0, 0, 0],
[0, 0, 0, 1],
[0, 0, 0, 0]
]
print(solve(matrix))

Đầu vào

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

Đầu ra

10