Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
BFS solution in Uncategorized category for Express Delivery by bryukh
from heapq import heappop, heappush
STEPS = {
"U": (-1, 0),
"D": (1, 0),
"L": (0, -1),
"R": (0, 1),
}
def possible_steps(field_map, x, y, box):
res = []
lx, ly = len(field_map), len(field_map[0])
if field_map[x][y] == "B":
res.append((x, y, not box, 1, "B"))
for step, dir in STEPS.items():
new_x, new_y = x + dir[0], y + dir[1]
if 0 <= new_x < lx and 0 <= new_y < ly and field_map[new_x][new_y] != "W":
res.append((new_x, new_y, box, 1 + box, step))
return res
def checkio(field_map):
queue = [(0, 0, 0, 1, "")] # time, row, col, hold_box, path)
closed = []
while queue:
t, x, y, box, path = heappop(queue)
if field_map[x][y] == "E" and box:
return path
if (x, y, box) in closed:
continue
closed.append((x, y, box))
for nx, ny, nbox, cost, act in possible_steps(field_map, x, y, box):
if (nx, ny, nbox) in closed:
continue
heappush(queue, (t + cost, nx, ny, nbox, path + act))
return "U"
#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
Comments: