网格图中最少访问的格子数

这个题解采用的是动态规划的思想，结合一种特殊的数据结构来优化搜索过程。从网格的右下角开始反向思考到达左上角的最小步数，使用两个列表来维护可能的移动路径和步数。对于每一个格子，计算向左和向上移动的最小步数，如果这个步数小于当前记录的步数，则更新。这种方法通过从右下到左上的方式，逐步缩减搜索空间，并在过程中不断更新每个格子到达终点的最小步数。

时间复杂度: O(m*n*log(n))

空间复杂度: O(m*n)

class Solution:
    def minimumVisitedCells(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        m1, n1 = m - 1, n - 1
        col_st = [[] for _ in range(n1)] + [[(m1, 1)]] # 列状态初始化
        st = [(n1, 1)] # 状态列表初始化
        for j in range(n1 - 1, -1, -1):
            p = st_remove(st, j + grid[m1][j])
            if p == inf:
                continue
            st.append((j, p)) # 更新状态列表
            col_st[j].append((m1, p)) # 更新列状态
        for i in range(m1 - 1, -1, -1):
            rst = [] # 行状态清空准备更新
            for j in range(n1, -1, -1):
                cst = col_st[j]
                p1, p2 = st_remove(cst, i + grid[i][j]), st_remove(rst, j + grid[i][j])
                if p2 < p1:
                    p1 = p2
                    st_remove_1(cst, p1)
                elif p2 > p1:
                    st_remove_1(rst, p1)
                elif p1 == inf:
                    continue
                cst.append((i, p1))
                rst.append((j, p1))
        st = col_st[0]
        return st[-1][1] if len(st) > 0 and st[-1][0] == 0 else -1

def st_remove(st, k):
    p = len(st) - 1
    if p < 0 or k < st[p][0]:
        return inf
    while p > 0 and k >= st[p - 1][0]:
        p -= 1
    del st[p + 1:]
    return st[p][1] + 1

def st_remove_1(st, k):
    p = len(st) - 1
    while p >= 0 and k <= st[p][1]:
        p -= 1
    del st[p + 1:]