Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Uncategorized category for Express Delivery by Amachua
from heapq import *
DIRECTION = {'U': (-1, 0), 'D': (1, 0), 'L': (0, -1), 'R': (0, 1)}
def checkio(field_map):
current_position, visited = [], []
"""
Add the first position in the queue. It is composed of four parameters:
- 0 : the time needed to reach this position;
- 2 : the move_cost needed to reach a neighbouring cells (2 if Stephan has the cargo and 1 otherwise);
- (0, 0) : the current position on the map;
- '' the succession of movements needed to reach the current position.
"""
heappush(current_position, (0, 2, (0, 0), ''))
while current_position:
time, move_cost, position, path = heappop(current_position)
# Don't re-evaluate a position already seen.
if [position, move_cost] in visited: continue
visited.append([position, move_cost])
for d, v in DIRECTION.items():
# Checks if the new position stays on the grid. If not, try with the other direction.
if not (0 <= position[0] + v[0] < len(field_map)): continue
if not (0 <= position[1] + v[1] < len(field_map[0])): continue
# Check if the new position is the goal and if Stephan has the cargo. If it is return the path to the goal.
if field_map[position[0] + v[0]][position[1] + v[1]] == 'E' and move_cost == 2: return path+d
# Check if the new position isn't water. If it's not add the value to the queue.
if field_map[position[0] + v[0]][position[1] + v[1]] != 'W':
heappush(current_position, (time + move_cost, move_cost, (position[0] + v[0], position[1] + v[1]), path+d))
# If the current case is a box, stephan can place the cargo in it. We update his current position without the cargo. i.e move_cost = 1
if field_map[position[0]][position[1]] == 'B':
heappush(current_position, (time + 1, 1 if move_cost == 2 else 2, (position[0], position[1]), path+'B'))
# The destination cannot be reached, let's sleep for a while.
return "SLEEP"
Jan. 8, 2014
