題目

Task

You are at start location [0, 0] in mountain area of NxN and you can only move in one of the four cardinal directions (i.e. North, East, South, West). Return minimal number of climb rounds to target location [N-1, N-1]. Number of climb rounds between adjacent locations is defined as difference of location altitudes (ascending or descending).

Location altitude is defined as an integer number (0-9).

我的答案

from heapq import *
from collections import defaultdict
from math import sqrt, floor

dirc = [[0, 1], [0, -1], [1, 0], [-1, 0]]

def dijkstra(edge, start, N):
    heap = []
    distance = [-1] * N
    distance[start] = 0
    heappush(heap, [start, distance[start]])
    while len(heap) > 0:
        d0 = heappop(heap)[0]
        if d0 == N - 1:
            return distance[d0]
        for i in range(len(edge[d0])):
            next = edge[d0][i][0]
            l = edge[d0][i][1]
            if distance[next] == -1 or distance[d0] + l < distance[next]:
                distance[next] = distance[d0] + l
                heappush(heap, [next, distance[next]])
    return distance[N - 1]

def path_finder(maze):
    print(maze)
    n = floor(sqrt(len(maze)))
    N = n * n
    edge = defaultdict(list)
    maze = [int(i) for i in list(maze) if i !='\n']
    for x in range(n):
        for y in range(n):
            for i in range(4):
                nx = x + dirc[i][0]
                ny = y + dirc[i][1]
                if nx < 0 or nx >= n or ny < 0 or ny >= n:
                    continue
                d = abs(maze[nx * n + ny] - maze[x * n + y])
                edge[x * n + y] += [[nx * n + ny, d]]
    return dijkstra(edge, 0, N)

其他精彩答案

def path_finder(maze):
    grid = maze.splitlines()
    end = h, w = len(grid) - 1, len(grid[0]) - 1
    bag, seen = {(0, 0): 0}, set()
    while bag:
        x, y = min(bag, key=bag.get)
        rounds = bag.pop((x, y))
        seen.add((x, y))
        if (x, y) == end: return rounds
        for u, v in (-1, 0), (0, 1), (1, 0), (0, -1):
            m, n = x + u, y + v
            if (m, n) in seen or not (0 <= m <= h and 0 <= n <= w): continue
            new_rounds = rounds + abs(int(grid[x][y]) - int(grid[m][n]))
            if new_rounds < bag.get((m, n), float('inf')): bag[m, n] = new_rounds

from heapq import *

def path_finder(maze):
    lst  = [ [int(c) for c in row] for row in maze.split('\n')]
    X, Y = len(lst), len(lst[0])
    end  = (X-1,Y-1)
    q, seens = [(0,end==(0,0),0,0)], {(0,0): 0}
    while q and not q[0][1]:
        c,_,x,y = heappop(q)
        for dx,dy in ((0,1), (0,-1), (1,0), (-1,0)):
            new = a,b = x+dx,y+dy
            if 0<=a<X and 0<=b<Y:
                dc = abs(lst[a][b] - lst[x][y])
                if seens.get(new, float("inf")) > c+dc:
                    heappush(q, (c+dc, new==end, a, b) )
                    seens[new] = c+dc
    return q[0][0]