LC 2577. 在网格图中访问一个格子的最少时间

https://leetcode.cn/problems/minimum-time-to-visit-a-cell-in-a-grid/

这题一个关键是，如果向相邻格子前进如果不满足条件的话，那么可以在过去路径上的两格来回走，每次+2.

其实这个就是格点上的奇偶性问题，并且这个是可以归纳出来的：

想清楚这个思路的之后就是dijkstra最短路搜索了。 

class Solution:
    def minimumTime(self, grid: List[List[int]]) -> int:
        n, m = len(grid), len(grid[0])
        if grid[0][1] > 1 and grid[1][0] > 1:
            return -1

        hp = []
        hp.append((0, 0, 0))
        inf = 1 << 30
        visit = [[inf] * m for _ in range(n)]

        import heapq
        while hp:
            (d, x, y) = heapq.heappop(hp)
            if (x, y) == (n - 1, m - 1):
                return d
            for dx, dy in ((-1, 0), (1, 0), (0, -1), (0, 1)):
                x2, y2 = x + dx, y + dy
                if 0 <= x2 < n and 0 <= y2 < m:
                    gap = grid[x2][y2] - (d + 1)
                    if gap <= 0:
                        value = d + 1
                    else:
                        value0 = d + 1 + (gap + 1) // 2 * 2
                        # 也可以是下面这种形式
                        value1 = grid[x2][y2] + (grid[x2][y2] - x2 - y2) % 2
                        value = value0
                    if visit[x2][y2] > value:
                        visit[x2][y2] = value
                        heapq.heappush(hp, (value, x2, y2))
        return -1

我觉得这个 题解 里面提到的二分方法也比较对，但是没有搞清楚为什么不work. 差别在于二分方式上，看上去需要确保解上有1个位置的空间 `left + 1 <= right`. 然后选择right.

我觉得这个解法里面vis特别巧妙，使用 `checktime` 来判断是否已经访问过，这样可以复用之前整个数组。 

class Solution:
    def minimumTime(self, grid: List[List[int]]) -> int:
        n, m = len(grid), len(grid[0])
        if grid[0][1] > 1 and grid[1][0] > 1:
            return -1

        # 将vis放在外面特别好，因为每次vis time是不同的
        vis = [[0] * m for _ in range(n)]

        def test(T):
            vis[-1][-1] = T
            from collections import deque
            dq = deque()
            dq.append((T, n - 1, m - 1))
            while dq:
                (t, x, y) = dq.popleft()
                if (x, y) == (0, 0):
                    return True
                for dx, dy in ((-1, 0), (1, 0), (0, -1), (0, 1)):
                    x2, y2 = x + dx, y + dy
                    if 0 <= x2 < n and 0 <= y2 < m and vis[x2][y2] != T and grid[x2][y2] <= (t - 1):
                        vis[x2][y2] = T
                        dq.append((t - 1, x2, y2))
            return False

        left = max(grid[-1][-1], m + n - 2) - 1
        right = max(map(max, grid)) + m + n
        while (left + 1) < right:
            t = (left + right) // 2
            if test(t):
                right = t
            else:
                left = t + 1
        ans = right
        ans = ans + (ans - m - n) % 2
        return ans