迷路を解けばいいの？

書いたら入社させてもらえるって風の噂で聞いたので書いてみた。正直迷路の解き方なんてDPしか知らないのでDPで。

import sys
import copy

def printMap(map):
    for line in map:
        for char in line:
            sys.stdout.write(char)
            if len(char) < 2:
                sys.stdout.write(' ')
        sys.stdout.write('\n')

def changeNeighbours(x, y, dpmap, nextmap, i):
    i += 1
    tgt = dpmap[y][x]
    if tgt is ' ':
        nextmap[y][x] = str(i)
    elif tgt is 'G':
        nextmap[y][x] = str(i)
        return True
    elif tgt is '*':
        return False
    elif int(tgt) > i:
        nextmap[y][x] = i
    return False

def inputNumber(x, y, next, dpmap, map):
    if (dpmap[y][x] is not '*' and dpmap[y][x] is not ' ') and int(dpmap[y][x]) == next:
        map[y][x] = '$'
        return True
    return False
    
def traceRoute(x, y, dpmap, map, sx, sy):
    if sx == x and sy == y:
        return True
    else:
        next = int(dpmap[y][x]) - 1
        if inputNumber (x, y-1, next, dpmap, map):
            return traceRoute(x, y-1, dpmap, map, sx, sy)
        if inputNumber (x, y+1, next, dpmap, map):
            return traceRoute(x, y+1, dpmap, map, sx, sy)
        if inputNumber (x-1, y, next, dpmap, map):
            return traceRoute(x-1, y, dpmap, map, sx, sy)
        if inputNumber (x+1, y, next, dpmap, map):
            return traceRoute(x+1, y, dpmap, map, sx, sy)

map = []

for line in sys.stdin:
    l = []
    for ch in line.rstrip():
        l.append(str(ch))
    map.append(l)

printMap(map)

maxX = len(map[0])
maxY = len(map)
for x in xrange(maxX):
    for y in xrange(maxY):
        if map[y][x] is 'S':
            start = (y, x)
        if map[y][x] is 'G':
            goal  = (y, x)

dpmap = copy.deepcopy(map)
dpmap[start[0]][start[1]] = "0"
nextmap = copy.deepcopy(dpmap)

i = 0
while 1:
    flag = False
    for x in xrange(maxX):
        for y in xrange(maxY):
            if dpmap[y][x] is '*' or dpmap[y][x] is 'G' or dpmap[y][x] is ' ':
                pass
            elif dpmap[y][x] == str(i):
                flag = changeNeighbours(x+1, y, dpmap, nextmap, i)
                flag = changeNeighbours(x-1, y, dpmap, nextmap, i)
                flag = changeNeighbours(x, y+1, dpmap, nextmap, i)
                flag = changeNeighbours(x, y-1, dpmap, nextmap, i)

    i += 1
    dpmap = nextmap
    if dpmap[goal[0]][goal[1]] is not "G":
        break

traceRoute(goal[1], goal[0], dpmap, map, start[1], start[0])
printMap(map)

なんというか、アドホック感が・・・