Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Very fast - BFS with heapq and Manhatten heuristics solution in Speedy category for Open Labyrinth by vikulin
# Finds one shortest path using Breadth-first search
# Heapq with Manhatten heuristics performs slightly better than deque
# Stores the shortest path to already visited cells in the original maze's matrix
from heapq import heappop, heappush
def checkio(maze):
MOVES = (("S", (1,0)), ("N", (-1,0)), ("W", (0,-1)), ("E", (0,1)))
maze[1][1] = ''
hq = [(0, (1,1))]
while hq:
_, (py, px) = heappop(hq)
for move, (dy, dx) in MOVES:
ny, nx = py + dy, px + dx
if ny == nx == 10:
return maze[py][px] + move
if not maze[ny][nx]:
maze[ny][nx] = maze[py][px] + move
heappush(hq, (20 - ny - nx, (ny, nx)))
return 'Error: there is no path between START and END'
Oct. 14, 2015