<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>

import collections as cl
import operator as op
import itertools as it
from dataclasses import dataclass

def walk(grid):
    (rows, cols) = map(len, (grid, grid[0]))

    for i in range(1, rows + cols):
        r = min(i, rows)
        start = max(0, i - rows)
        end = min(i, cols - start, rows)
        for j in range(end):
            yield (r - j - 1, start + j)

def up_and_left(x, y):
    yield from (
        (x - 1, y),
        (x, y - 1),
    )

@dataclass(frozen=True)
class Position:
    x: int
    y: int

    def move(self, direction):
        (x, y) = (direction(z, 1) for z in (self.x, self.y))
        yield from it.starmap(type(self), (
            (x, self.y),
            (self.x, y),
        ))

    def down_and_right(self):
        yield from self.move(op.add)

    def up_and_left(self):
        yield from self.move(op.sub)

def diagwalk(grid):
    bfs = cl.deque()
    visited = set()
    pos = Position(0, 0)
    end = Position(*(map(len, (grid, grid[0]))))

    bfs.append(pos)
    while bfs:
        pos = bfs.popleft()
        if pos not in visited:
            yield pos
            for p in pos.down_and_right():
                if 0 <= p.x < end.x and 0 <= p.y < end.y:
                    bfs.append(p)
            visited.add(pos)

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        last = Position(*(len(x) - 1 for x in (grid, grid[0])))

        for p in diagwalk(grid):
            smaller = None
            for ul in p.up_and_left():
                if ul.x >= 0 and ul.y >= 0:
                    value = grid[ul.x][ul.y]
                    if smaller is None or value < smaller:
                        smaller = value
            if smaller is not None:
                grid[p.x][p.y] += smaller

        return grid[last.x][last.y]
24200