Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Dijkstra variation solution in Uncategorized category for Express Delivery by nickie
from heapq import heappush, heappop
possible_moves = [(0,1,'R'), (0,-1,'L'), (1,0,'D'), (-1,0,'U'), (0,0,'B')]
def checkio(maze):
# Dimensions and find the start
N, M = len(maze), len(maze[0])
start = next((i, j) for (i, row) in enumerate(maze)
for (j, cell) in enumerate(row) if cell == 'S')
# Dijkstra with two possible states for each cell: loaded or not
q = []
heappush(q, (0, True, start))
prev = dict()
prev[True, start] = None
while q:
moves, loaded, (i, j) = heappop(q)
if maze[i][j] == 'E' and loaded:
break
for (di, dj, move) in possible_moves:
if move == 'B' and maze[i][j] != 'B':
continue
newLoaded = not loaded if move == 'B' else loaded
if 0 <= i+di < N and 0 <= j+dj < M and maze[i+di][j+dj] != 'W' \
and (newLoaded, (i+di, j+dj)) not in prev:
cost = 2 if loaded and move != 'B' else 1
prev[newLoaded, (i+di, j+dj)] = (i, j, move)
heappush(q, (moves+cost, newLoaded, (i+di, j+dj)))
# Reconstruct the solution
answer = []
while prev[loaded, (i, j)] != None:
(i, j, move) = prev[loaded, (i, j)]
loaded = not loaded if move == 'B' else loaded
answer.append(move)
return ''.join(reversed(answer))
#These "asserts" using only for self-checking and not necessary for auto-testing
if __name__ == '__main__':
checkio(["S...", "....", "B.WB", "..WE"]) # RRRDDD
checkio(["S...", "....", "B..B", "..WE"]) # DDBRRRBD
Jan. 8, 2014
