Python3 - заполнить массив из 2-х измерений расстоянием до одного элемента

Question

Я работаю над разрешением лабиринта. Я должен найти кратчайший путь лабиринта и вернуть строку, как "LLURD" (с указанием направления). Чтобы решить эту проблему, я разложил ее на несколько этапов. Один из них заключается в том, чтобы взять исходную сетку и вернуть сетку, в которой все ячейки помечены числом, которое является расстоянием от этой ячейки до начальной точки.

Я думаю, что пример более понятен:
Ввод:

[0,0,0, #, 0]
[0, X, 0,0,0]
[0, #, 0,0 , 0]
[0,0,0, #, 0]

«X» - это начальная точка
«#» - это стена
Мы можем двигаться вверх, вниз, вправо Левый

Выход:

[2,1,2, #, 4]
[1, X, 1,2,3]
[2, #, 2,3,4]
[3,4,3, #, 5]

Может ли кто-нибудь помочь мне в этом?

Спасибо

Answer 1

Если мы представим двумерную сетку в плоскости xy, расстояние между двумя узлами - это расстояние в плоскости x плюс расстояние в плоскости y.

g=[[0,0,0,'#',0],
[0,'X',0,0,0],
[0,'#',0,0,0],
[0,0,0,'#',0]]

def get_dist(start,end): #pass tuples of x,y
    x1,y1=start
    x2,y2=end
    return abs(x1-x2)+abs(y1-y2)

def find_start(g): #if you already have it, ignore
    for y,col in enumerate(g):
        for x,item in enumerate(col):
            if item=='X':
                return x,y

start = find_start(g)
for y,col in enumerate(g):
    for x,item in enumerate(col):
        if item == 0: #if is not a start or wall
            g[y][x]=get_dist(start,(x,y))

, которое возвращает

[2, 1, 2, '#', 4]
[1, 'X', 1, 2, 3]
[2, '#', 2, 3, 4]
[3, 2, 3, '#', 5]