maze.py

#!/usr/bin/python

import sys,os

START = 0
WALL  = 1
GOAL  = 2
OPEN  = 3

class Maze(object):
    def __init__(self, input):
        self.__text = [ln.strip() for ln in input]
        self.__height = len(self.__text)
        self.__width  = len(self.__text[0])
        self.__dist = []
        self.__route = []
        for i in range(self.__height):
            self.__dist.append([None] * self.__width)

        for i in range(self.__height):
            for j in range(self.__width):
                if self.__text[i][j] == "S":
                    self.start = (i,j)
                elif self.__text[i][j] == "G":
                    self.goal = (i,j)

    def cell_type(self, i, j):
        c = self.__text[i][j]
        if   c == "*": return WALL
        elif c == ' ': return OPEN
        elif c == 'G': return GOAL
        elif c == 'S': return START
        else: raise RuntimeError, "unknown cell type at (%d,%d) = %s" % (i,j,c)

    def display(self):
        print
        for i in range(self.__height):
            for j in range(self.__width):
                if self.cell_type(i,j) == OPEN:
                    if (i,j) in self.__route:
                        sys.stdout.write("$")
                    else:
                        sys.stdout.write(" ")
                else:
                    sys.stdout.write(self.__text[i][j])
            print

    def distance(self, i, j):
        if i < 0 or i >= self.__height: return None
        if j < 0 or j >= self.__width:  return None

        if   self.cell_type(i,j) == START: return 0
        elif self.cell_type(i,j) == OPEN:
            return self.__dist[i][j]
        else:
            return None

    def calc_distance(self):
        while True:
            changed = False
            for i in range(self.__height):
                for j in range(self.__width):
                    if self.cell_type(i,j) == OPEN:
                        north = self.distance(i-1,j)
                        south = self.distance(i+1,j)
                        east  = self.distance(i,j-1)
                        west  = self.distance(i,j+1)

                        # neighbors
                        nbrs = filter(lambda x: x!=None, [north,south,east,west])

                        if len(nbrs) > 0:
                            m = min(nbrs) + 1
                            if self.__dist[i][j] is None or m < self.__dist[i][j]:
                                self.__dist[i][j] = m
                                changed = True

            if not changed: break

    def route(self):
        # Find the shortest route from the goal to the start
        i,j = self.goal

        while self.start != (i,j):
            self.__route.append((i,j))
            north = self.distance(i-1,j)
            south = self.distance(i+1,j)
            west  = self.distance(i,j-1)
            east  = self.distance(i,j+1)

            m = min(filter(lambda x:x != None, [north, south, west ,east]))
            if   north == m: i = i - 1
            elif south == m: i = i + 1
            elif west  == m: j = j - 1
            elif east  == m: j = j + 1
            else: raise RuntimeError, 'ERROR'

            self.__route.append((i,j))

def main():
    maze = Maze(sys.stdin.readlines())
    maze.display()
    maze.calc_distance()
    maze.route()
    maze.display()

if __name__ == "__main__":
    main()