<p>Given a <code>m x n</code> <code>grid</code> filled with non-negative numbers, find a path from top left to bottom right, which minimizes the sum of all numbers along its path.</p>

<p><strong>Note:</strong> You can only move either down or right at any point in time.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/11/05/minpath.jpg" style="width: 242px; height: 242px;" />
<pre>
<strong>Input:</strong> grid = [[1,3,1],[1,5,1],[4,2,1]]
<strong>Output:</strong> 7
<strong>Explanation:</strong> Because the path 1 &rarr; 3 &rarr; 1 &rarr; 1 &rarr; 1 minimizes the sum.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> grid = [[1,2,3],[4,5,6]]
<strong>Output:</strong> 12
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>m == grid.length</code></li>
	<li><code>n == grid[i].length</code></li>
	<li><code>1 &lt;= m, n &lt;= 200</code></li>
	<li><code>0 &lt;= grid[i][j] &lt;= 200</code></li>
</ul>

from queue import PriorityQueue

class Solution:

    def findMinPath(self, w:int, x:int, y:int, grid: List[List[int]]) -> int:
        N = len(grid)
        M = len(grid[0])

        #print(f"Call {x} {y}")

        w = w + grid[y][x]

        if y == N -1 and x == M -1:
            return w
        
        if x == M -1:
            return self.findMinPath(w,x,y+1,grid)

        if y == N -1:
            return self.findMinPath(w,x+1,y,grid)

        w1 = self.findMinPath(w,x,y+1,grid)
        w2 = self.findMinPath(w,x+1,y,grid)

        return w1 if w1 < w2 else w2


    def minPathSum(self, grid: List[List[int]]) -> int:
        #return self.findMinPath(0,0,0,grid)

        N = len(grid)
        M = len(grid[0])

        node_to_visit = PriorityQueue()
        node_to_visit.put((0,0),grid[0][0])

        visited = {0:{0:grid[0][0]}}

        while not node_to_visit.empty():
            y,x = node_to_visit.get()
            w = visited[y][x]
            print(f"Visiting {y},{x}, w: {w}")

            for neigh in [(1,0),(0,1)]:
                x1, y1 = x + neigh[1], y + neigh[0]
                if x1 >= M or y1 >= N:
                    #out of matrix
                    continue

                nw = w + grid[y1][x1]
                if y1 not in visited:
                    visited[y1] = {}

                if x1 not in visited[y1]:
                    node_to_visit.put((y1,x1),nw)
                    visited[y1][x1] = nw

                elif visited[y1][x1] > nw:
                    node_to_visit.put((y1,x1),nw)
                    visited[y1][x1] = nw

        return visited[N-1][M-1]
20200