Python의 주어진 행렬에서 수집할 수 있는 최대 동전 양을 찾는 프로그램

행렬 [r, c]가 해당 셀의 동전 수를 나타내는 2D 행렬이 있다고 가정합니다. 우리는 모든 위치에서 시작할 수 있으며 4 방향(대각선이 아닌 위, 아래, 왼쪽 및 오른쪽) 중 하나를 움직여 코인을 수집하고 싶습니다. 셀로 이동하면 코인이 수집되고 해당 셀의 값은 0이 됩니다. 0코인이 있는 셀은 방문할 수 없으므로 최대 모을 수 있는 코인의 양을 찾아야 합니다.

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

그러면 2 −> 3 −> 6 −> 4 −> 3

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

• 행렬이 비어 있으면

  • 0 반환

• n :=행렬의 행 개수, m :=매트의 열 개수

• x :=[−1, 1, 0, 0]과 같은 목록, y :=[0, 0, −1, 1]과 같은 목록

• util() 함수를 정의합니다. 이것은, b

• ret :=0

• 범위 0에서 3까지의 k에 대해 수행

  • (t1, t2) :=(x[k] + a, y[k] + b)

  • (t1, t2)가 유효한 셀이면

    • t :=매트[t1, t2], 매트[t1, t2] :=0

    • ret :=ret의 최대값 및 (util(t1, t2) + t)

    • 매트[t1, t2] :=t

• 리턴 렛

• 주요 방법에서 다음을 수행하십시오 -

• 해상도 :=0

• 0 ~ n − 1 범위의 i에 대해 다음을 수행합니다.

  • 0 ~ m − 1 범위의 j에 대해 다음을 수행합니다.

    • mat[i, j]가 0이 아니면

      • t :=매트[i, j], 매트[i, j] :=0

      • res :=최대 res 및 (util(i, j) + temp)

• 반환 해상도

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

예시

class Solution:
   def solve(self, mat):
      if not mat:
         return 0
      n, m = len(mat), len(mat[0])
      x, y = [−1, 1, 0, 0], [0, 0, −1, 1]
      def ok(a, b):
         return 0 <= a < n and 0 <= b < m and mat[a][b]
      def util(a, b):
         ret = 0
         for k in range(4):
            t1, t2 = x[k] + a, y[k] + b
            if ok(t1, t2):
               t, mat[t1][t2] = mat[t1][t2], 0
               ret = max(ret, util(t1, t2) + t)
               mat[t1][t2] = t
            return ret
         res = 0
         for i in range(n):
            for j in range(m):
               if mat[i][j]:
                  temp, mat[i][j] = mat[i][j], 0
                  res = max(res, util(i, j) + temp)
         return res
ob = Solution()
matrix = [
   [2, 4, 3],
   [3, 6, 0],
   [2, 0, 12]
]
print(ob.solve(matrix))

입력

[
[2, 4, 3],
[3, 6, 0],
[2, 0, 12] ]

출력

18