l1.txt

#########################
# # #   #      # #      #
#   # # # # ## #   #### #
# # ### # # #S # # ## # #
# #       # #### #    # #
# ######### #    # #### #
# #    # #### # ##    # #
# # ####    # # #  #### #
# # # ##### # # ####    #
#           ### #    ####
######### ###   # ####  #
#  #      #   # # # ## ##
# ##### ####### #      ##
#     #         # #######
##### ###########       #
#          #      ##### #
# ### # ###########     #
# #   #     ##      ### #
# ###########  # # ######
#       #     ## #      #
# ####### ######## ## # #
#         #      # #### #
### ########## ### # ## #
###        #       #    #
############E############

labirynth.py

import time

class Tile:
    def __init__(self, passable=False):
        self.passable = passable
        self.steps = float("inf")

    def __bool__(self):
        return self.passable


def create(f):
    start = None
    end = None
    tiles = [ [Tile()]*25 for i in range(25) ]

    for y, row in enumerate(f):
        for x, tile in enumerate(row.strip()):
            if tile in (' ', 'S', 'E'):
                tiles[y][x] = Tile(True)

            if tile == 'S':
                start = (y,x)

            if tile == 'E':
                end = (y,x)

    return tiles, start, end


def show_walk(tiles, start, end, solution):
    print("\x1b[2J", end='')
    for y, row in enumerate(tiles):
        for x, tile in enumerate(row):
            if (y,x) == end:
                print("\x1b[1;31m  @  ", end='')
            elif (y, x) in solution:
                print("\x1b[0m  +  ", end='')
            elif tile:
                print("\x1b[0m{0:5}".format(tile.steps), end='')
            else:
                print("\x1b[1;30m#####", end='')
        print()
    time.sleep(0.2)

def show_steps(tiles, start, end):
    print("\x1b[2J", end='')
    for y, row in enumerate(tiles):
        for x, tile in enumerate(row):
            if (y,x) == start:
                print("\x1b[1;31m  @  ", end='')
            elif (y,x) == end:
                print("\x1b[1;32m  E  ", end='')
            elif tile:
                if tile.steps == float("inf"):
                    print("\x1b[0m   . ", end='')
                else:
                    print("\x1b[0m{0:5}".format(tile.steps), end='')
            else:
                print("\x1b[1;30m#####", end='')
        print()
    time.sleep(0.2)

solution.py

#!/usr/bin/env python3
# encoding: utf-8


def solve(tiles, start, end, show_find, show_walk):
    # diagonal movement is forbidden
    DIRECTIONS = [ (-1,0), (0,1), (1,0), (0, -1) ]

    def find_exit(tiles, start, steps=0):
        show_find(tiles, start, end)

        # unpack coordinates
        y, x = start

        # first and foremost, save number of steps in which tile at (y,x) can
        # be reached
        tiles[y][x].steps = steps

        # if we're at the end, just stop
        if start == end:
            return

        def check_direction(dy, dx):
            # consider a direction if:
            #  - tile at (y+dy, x+dx) is passable
            #  - number of steps in which that tile can be reached is *greater*
            #    than current steps + 1
            if tiles[y+dy][x+dx] and tiles[y+dy][x+dx].steps > tiles[y][x].steps + 1:
                find_exit(tiles, (y+dy, x+dx), steps+1)

        # make sure to check all directions
        for dy, dx in DIRECTIONS:
            check_direction(dy, dx)

    # fill in table of steps
    find_exit(tiles, start)

    def walk(tiles, end):
        solution = []

        # walk the table backwards from end to to the start
        while end != start:
            y, x = end

            # save each coordinate we visit
            solution.append(end)
            show_walk(tiles, start, end, solution)

            # for each direction, find number of steps in that direction
            # steps
            candidates = {}
            for dy, dx in DIRECTIONS:
                # make sure not to leave the map ;)
                if 0 <= y+dy <= 24 and 0 <= x+dx <= 24:
                    candidates[(y+dy,x+dx)] = tiles[y+dy][x+dx].steps

            # select direction that gives us the smallest number of steps
            end = min(candidates, key=candidates.get)

        solution.append(end)
        show_walk(tiles, start, end, solution)
        return solution

    return walk(tiles, end)


if __name__ == '__main__':
    import sys
    import labirynth

    tiles, start, end = labirynth.create(open(sys.argv[1]))
    solution = solve(tiles, start, end, labirynth.show_steps, labirynth.show_walk)