Untitled
def nearest_cell(arr, p1 ,p2): n = len(arr) def djikstra(arr, start): dp = [float('inf') for _ in range(n)] dp[start] = 0 q = [(0, start)] visit = set() while q: cost, node = q.pop(0) if node in visit: continue dp[node] = cost visit.add(node) if arr[node] == -1: continue q.append((cost+1, arr[node])) return dp d1 = djikstra(arr,p1) d2 = djikstra(arr, p2) d= [float('inf') for _ in range(n)] for i in range(n): tmp = d1[i] + d2[i] d[i] = tmp return min( list(range(i)), key = lambda x: (d[x], x))
Leave a Comment