Anonymous

#!/usr/bin/python
# -*- coding: utf-8 -*-

import sys
import re
import string
import array
import Queue

go, stop, start, end, lane = range(5)

class Vertex(object):
	__slots__ = "typ adj dist visited".split()
	def __init__(self):
		self.typ = stop
		self.adj = []
		self.dist = -1
		self.visited = False

class ShortestPath:
	def __init__(self, matrix, vstart, vend):
		self.matrix = matrix
		self.start = vstart
		self.end = vend
		self.createGraph()
		self.bfs()
		self.makePath()

	def makePath(self):
		breaked = False
		vertex = self.end
		while vertex != self.start:
			for i in range(len(vertex.adj)):
				breaked = False
				if vertex.adj[i].dist == vertex.dist - 1:
					if not vertex == self.end:
						vertex.typ = lane
					vertex = vertex.adj[i]
					breaked = True
					break
			if not breaked:
				print "there is no way."
				sys.exit()

	def bfs(self):
		self.start.visited = True
		self.start.dist = 0
		queue = Queue.Queue(0)
		queue.put(self.start)
		while not queue.empty():
			u = queue.get()
			for i in range(len(u.adj)):
				v = u.adj[i]
				if not v.visited:
					v.visited = True
					v.dist = u.dist + 1
					queue.put(v)

	def createGraph(self):
		dir = [[1,1], [0,1], [-1,1], [1,0], [-1,0], [1,-1], [0,-1], [-1,-1]]
		
		for x in range(len(self.matrix)):
			for y in range(len(self.matrix[x])):
				for i in range(len(dir)):
					try:
						nx = x + dir[i][0]
						ny = y + dir[i][1]
						next = self.matrix[nx][ny]
					except IndexError:
						continue
					
					if nx >= 0 and ny >= 0 and not next.typ == stop:
						self.matrix[x][y].adj.append(next)
		
	def printMatrix(self):
		for x in range(len(self.matrix)):
			for y in range(len(self.matrix[x])):
				typ = self.matrix[x][y].typ
				if typ == start:
					sys.stdout.write('S')
				if typ == end:
					sys.stdout.write('E')
				if typ == go:
					sys.stdout.write('0')
				if typ == stop:
					sys.stdout.write('#')
				if typ == lane:
					sys.stdout.write('.')
			print

def main():
	usage = "Usage: ./shortest_path.py filename"
	if len(sys.argv) == 1:
		print usage
	else:
		try:
			file = open(sys.argv[1])
			matrix = []
			for line in file:
				matrix.append([])
				for char in line:
					if char != '\n':
						vertex = Vertex()
						matrix[-1].append(vertex)
						if char == '0':
							vertex.typ = go
						elif char == 'S':
							vertex.typ = start
							vstart = vertex
						elif char == 'E':
							vertex.typ = end
							vend = vertex
			file.close()
			path = ShortestPath(matrix, vstart, vend)
			path.printMatrix()
		except IOError:
			print "No such file or directory: '" + sys.argv[1] + "'"
			print usage

if __name__ == "__main__":
	main()