人材獲得作戦・４を解答してみた

物議を醸している下記の問題
人生を書き換える者すらいた。: 人材獲得作戦・４　試験問題ほか
なかなかの良問だと思ったのでPythonで解答してみた．かかった時間は１時間ぐらい．

#!/usr/bin/env python2.6
from __future__ import print_function
import sys

def printmaze(maze):
    for line in maze:
        print(''.join(line))

def neighbours(x,y):
    return ((x-1,y),(x+1,y),(x,y-1),(x,y+1))

def find(c, maze):
    for i,line in enumerate(maze):
        try:
            j = line.index(c)
            return i,j
        except ValueError:
            pass

def trace(maze, goal, length):
    node = goal
    while length > 1:
        for x,y in neighbours(*node):
            if maze[x][y] == length-1:
                node = (x, y)
                maze[x][y] = '$'
                break
        length -= 1
    for i in range(len(maze)):
        for j in range(len(maze[0])):
            if type(maze[i][j]) is int:
                maze[i][j] = ' '
    printmaze(maze)

def main():
    maze = [list(line.strip('\n')) for line in sys.stdin]
    nodes = [find('S', maze)]
    length = 1
    while nodes:
        new_nodes = []
        for node in nodes:
            new_neighbours = neighbours(*node)
            for new_neighbour in new_neighbours:
                x,y = new_neighbour
                if maze[x][y] == ' ':
                    maze[x][y] = length
                    new_nodes.append((x,y))
                elif maze[x][y] == 'G':
                    trace(maze, (x,y), length+1)
                    exit()
        length += 1
        nodes = new_nodes

if __name__ == '__main__':
    main()

綺麗に書けたつもりではいるが，まだ自分には時間をかけて深く考えすぎてしまう癖があるようだ．