Laberinto

from math import inf

# Get the neighbors of a cell if they are not walls and the value of the cell is worse (greater) than the value of the neighbor
def get_neighbors(i, j, lab, inverse=False):
    rows = len(lab)
    cols = len(lab[0])

    neighbors = []
    
    # If inverse is True, the value of the cell will subtract 3 
    # - we substract 1 because of the step is the previous value of the cell, 
    # - we substract another 1 because the value of the cell is added one (+1) for the comparison
    # - we substract another 1 since the compairson is made with a "<" and not with a "<=" 
    curr_val = lab[i][j] if not inverse else lab[i][j] - 3  
    
    movement = [(0, 1), (0, -1), (1, 0), (-1, 0)]

    for m in movement:
        new_i = i + m[0]
        new_j = j + m[1]
        if 0 <= new_i < rows and 0 <= new_j < cols and lab[new_i][new_j] != "#":
            if curr_val + 1 < lab[new_i][new_j]:
                neighbors.append((new_i, new_j))

    return neighbors

# Check if the cell is the end of the labyrinth
def reached_end(i, j, lab):
    return i == len(lab) - 1 and j == len(lab[0]) - 1

# Backtracking algorithm to find the best path in the labyrinth
def backtracking_lab(i, j, lab, step=0):
    
    # Update the value of the cell (this should be the best value so far, since we only the best path is returned by the function get_neighbors()
    lab[i][j] = step
    
    # Base case (reached the end of the labyrinth)
    if reached_end(i, j, lab):
        return
    
    ngs = get_neighbors(i, j, lab)

    for ng in ngs:
        backtracking_lab(ng[0], ng[1], lab, step + 1)

def get_best_path(lab, to):
    step = lab[-1][-1]
    
    if step == inf:
        return []
    
    i = len(lab) - 1
    j = len(lab[0]) - 1
    
    path = [(i, j)]
    
    while step != to:
        ngs = get_neighbors(i, j, lab, inverse=True)
        for ng in ngs:
            if lab[ng[0]][ng[1]] == step - 1:
                step -= 1
                i = ng[0]
                j = ng[1]
                path.append((i, j))
                break
            
    return path
        
# Print the labyrinth
def print_lab(lab):
    n = len(str(lab[-1][-1])) + 1
    path = get_best_path(lab, 1)
    for row in range(len(lab)):
        for col in range(len(lab[0])):
            cell = lab[row][col]    
            char = cell if (row, col) in path else "·"
            char = "#" if cell == "#" else char
            print(f"{char:^{n}}", end="")
        print()

# ============================================================================
if __name__ == "__main__":
    lab = [[inf,inf,"#",inf,inf,inf,"#",inf,inf,inf,"#",inf,inf,inf,inf],["#",inf,"#",inf,"#",inf,"#",inf,"#",inf,"#",inf,"#",inf,"#"],[inf,inf,"#",inf,"#",inf,"#",inf,"#",inf,"#",inf,"#",inf,inf],[inf,"#","#",inf,"#",inf,"#",inf,"#",inf,"#",inf,"#","#",inf],[inf,inf,"#",inf,"#",inf,"#",inf,"#",inf,"#",inf,"#",inf,inf],["#",inf,"#",inf,"#",inf,"#",inf,"#",inf,"#",inf,"#",inf,"#"],[inf,inf,"#",inf,"#",inf,"#",inf,"#",inf,"#",inf,"#",inf,inf],[inf,"#","#",inf,"#",inf,"#",inf,"#",inf,"#",inf,"#","#",inf],[inf,inf,"#",inf,"#",inf,"#",inf,"#",inf,"#",inf,"#",inf,inf],["#",inf,"#",inf,"#",inf,"#",inf,"#",inf,"#",inf,"#",inf,"#"],[inf,inf,inf,inf,"#",inf,inf,inf,"#",inf,"#",inf,"#",inf,inf],["#","#","#","#","#","#","#","#","#",inf,"#",inf,"#","#",inf],[inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,"#",inf,"#",inf,inf],[inf,"#","#","#","#","#","#","#","#","#","#",inf,"#",inf,"#"],[inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,"#",inf,inf]]

    # Start the backtracking algorithm from the start point (0, 0)
    start_i = 0
    start_j = 0
    print_lab(lab)
    print("----")
    backtracking_lab(start_i, start_j, lab, step=1)
    print("----")
    
    # Print the labyrinth
    print_lab(lab)