LC-2577 Hard LeetCode

2577. Minimum Time to Visit a Cell In a Grid

Array Breadth-First Search Graph Heap (Priority Queue) Matrix Shortest Path

Read the full problem statement on LeetCode.

Difficulty: hard Acceptance: 57% Topics: Array, Breadth-First Search, Graph, Heap (Priority Queue), Matrix, Shortest Path

View full problem on LeetCode

Reading material

Arrays & Hashing 12 min Trees & Traversals 18 min Graphs 16 min

Reference solution (spoiler · python)

# Time:  O(m * n * log(m * n))
# Space: O(m * n)

import heapq


# dijkstra's algorithm
class Solution(object):
    def minimumTime(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        DIRECTIONS = ((1, 0), (0, 1), (-1, 0), (0, -1))
        def dijkstra(start, target):
            best = [[float("inf")]*len(grid[0]) for _ in xrange(len(grid))]
            best[start[0]][start[1]] = 0
            min_heap = [(0, start[0], start[1])]
            while min_heap:
                curr, i, j = heapq.heappop(min_heap)
                if best[i][j] < curr:
                    continue
                if (i, j) == target:
                    break
                for di, dj in DIRECTIONS:  
                    ni, nj = i+di, j+dj   
                    if not (0 <= ni < len(grid) and 0 <= nj < len(grid[0]) and best[ni][nj] > max(grid[ni][nj]+int(grid[ni][nj]%2 == best[i][j]%2), curr+1)):
                        continue
                    best[ni][nj] = max(grid[ni][nj]+int(grid[ni][nj]%2 == best[i][j]%2), curr+1)
                    heapq.heappush(min_heap, (best[ni][nj], ni, nj))
            return best[target[0]][target[1]]

        if min(grid[0][1], grid[1][0]) > 1:
            return -1
        return dijkstra((0, 0), (len(grid)-1, len(grid[0])-1))

Solution from kamyu104/LeetCode-Solutions · MIT