Question

Code

• O(nk) algorithm, search all k state in each grid
• K also needs to be in visited set, since can visited same grid with different state

class Solution(object):
    def shortestPath(self, grid, k):
        row, col = len(grid), len(grid[0])

        q = deque([(0, (0, 0, k))])
        visit = set([(0, 0, k)])

        direction = [0, 1, 0, -1, 0]

        while q:
            steps, (r, c, removed) = q.popleft()

            if r == row - 1 and c == col - 1:
                return steps

            for i in range(4):
                new_r, new_c = r + direction[i], c + direction[i + 1]

                if new_r < 0 or new_r >= row or new_c < 0 or new_c >= col:
                    continue

                new_removed = removed - grid[new_r][new_c]
                new_state = (new_r, new_c, new_removed)

                if new_removed < 0 or new_state in visit:
                    continue

                q.append((steps + 1, new_state))
                visit.add(new_state)

        return -1