Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Uncategorized category for Digging a Canal by Moff
def neighbours(m, i, j):
delta = [(0, 1), (0, -1), (1, 0), (-1, 0)]
return [(ci, cj) for ci, cj in ((i + di, j + dj) for di, dj in delta)
if 0 <= ci < len(m) and 0 <= cj < len(m[0])]
def dijkstra(m, start, end):
vertex = {(r, c) for r in range(len(m)) for c in range(len(m[0]))}
distance = dict.fromkeys(vertex, float('inf'))
distance[start] = 0
while vertex:
r, c = min(vertex, key=distance.get)
vertex.remove((r, c))
for i, j in neighbours(m, r, c):
distance[(i, j)] = min(distance[(i, j)], distance[(r, c)] + m[i][j])
return distance.get(end)
def checkio(m):
h, w = len(m), len(m[0])
m.insert(0, [0] * w)
m.append([0] * w)
return dijkstra(m, (0, 0), (len(m) - 1, 0))
Sept. 2, 2015
