Max Heap (Dijekstra) Solution - Python
Intuition\nFor 0, 0 start calculate diagonal\n\nFor topRight and bottomRight, use minHeap to calculate the best option for each iteration.\n\n# Time Complexity\
# Intuition\nFor 0, 0 start calculate diagonal\n\nFor topRight and bottomRight, use minHeap to calculate the best option for each iteration.\n\n# Time Complexity\nO(n^2 log n)\n# Space Complexity\nO(n^2)\n\n# Code\n```python3 []\nclass Solution:\n    def maxCollectedFruits(self, fruits: List[List[int]]) -> int:\n\n        n = len(fruits)\n\n        ans = 0\n\n        for i in range(n):\n            ans += fruits[i][i]                \n\n        x, y = 0, n - 1\n        q = [[-fruits[x][y], x, y]]\n        topRightBest = 0\n        heapq.heapify(q)\n        seen = {}\n\n        while q:\n            temp = []\n            for _ in range(len(q)):\n                f, x, y = heapq.heappop(q)\n                \n                if (x,y) in seen and seen[(x,y)] >= -f:\n                    continue\n\n                if x == n - 1 and x == y:\n                    topRightBest = -f\n                    break\n                    \n                seen[(x,y)] = -f \n\n                for i, j in [(x+1, y-1), (x+1, y), (x+1, y+1)]:\n\n                    if i < 0 or j < 0 or i >= n or j >= n: continue\n                    if j < i: continue\n                    if j == i: \n                        heapq.heappush(temp, [f, i, j])\n                    else:\n                        heapq.heappush(temp, [f - fruits[i][j], i, j])\n            q = temp\n            if topRightBest != 0:\n                break\n\n        ans += topRightBest\n\n        x, y = n - 1, 0\n        q = [[-fruits[x][y], y, x]]\n        heapq.heapify(q)\n        bottomRightBest = 0\n        seen = {}\n\n        while q:\n            temp = []\n            for _ in range(len(q)):\n                f, y, x = heapq.heappop(q)\n                \n                if (x,y) in seen and seen[(x,y)] >= -f:\n                    continue\n\n                if x == n - 1 and x == y:\n                    bottomRightBest = -f\n                    break\n                    \n                seen[(x,y)] = -f \n                \n                for i, j in [(x-1, y+1), (x, y+1), (x+1, y+1)]:\n\n                    if i < 0 or j < 0 or i >= n or j >= n: continue\n                    if j > i: continue\n                    if j == i: \n                        heapq.heappush(temp, [f, j, i])\n                    else:\n                        heapq.heappush(temp, [f - fruits[i][j], j, i])\n            q = temp\n            if bottomRightBest != 0: \n                break\n            \n        ans += bottomRightBest\n\n        return ans\n\n\n```
['Python3']