gistfile1.py

#! -*- coding:utf-8 -*-
# 元ネタ http://okajima.air-nifty.com/b/2010/01/post-abc6.html
# 入力テキストは元ネタをコピペして保存でもしてください
import copy
def load(filename):
    f = open(filename,"r")
    mazes = []
    start = []
    end   = []
    min = []
    y = 0
    for line in f:
        x = 0
        mazec = []
        minc  = []
        for l in line:
            mazec.append(l)
            if l == "S":
                start = [ x, y ]
            if l == "G":
                end = [ x, y ]
            x += 1
            minc.append(10000)
        mazes.append(mazec[:-1])
        min.append(minc[:-1])
        y += 1
    for m in mazes:
        print m
    print start, end
    return mazes, start, end, min

def cond( maze, next,history, min):
    #print maze[next[1]][next[0]]
    if maze[next[1]][next[0]] == ' ':
        #print history
        for h in history:
            if (h[0] == next[0] and h[1] == next[1]):
                return False
        if min[next[1]][next[0]] <= len(history)+1: return False
        return True
    else: return False

def move( maze, now, end, history, min, x, y):
    #print "move", now
    next = [ now[0] + y, now[1] + x]
    if (next[0] == end[0] and next[1] == end[1]):
        history.append(now)
        print "goal"
        now = next
        return True
    elif cond( maze, next,history,min ):
        h = copy.deepcopy(history)
        h.append(now)
        min[now[1]][now[0]] = len(history)
        moves( maze, next, end, h, min )
    return False

def search(maze, start, end, min):
    now = start
    history = []
    # 移動の選択
    moves( maze, now, end, history, min)
    #output( maze, best)

def moves( maze, now, end, history, min):
    flag = move( maze, now, end, history, min, 0, -1)
    if (flag == True):
        goal(maze,history)

    flag = move( maze, now, end, history, min, 0, 1)
    if (flag == True):
        goal(maze,history)

    flag = move( maze, now, end, history, min, 1, 0)
    if (flag == True):
        goal(maze,history)

    flag = move( maze, now, end, history, min, -1,0)
    if (flag == True):
        goal(maze,history)

    #history.pop()
    return False

def goal( maze, history ):
    m2 = copy.deepcopy(maze)
    for h in history[1:]:
        m2[h[1]][h[0]] = '$'
    #print history
    for m in m2:
        for mm in m:
            print mm,
        print ""
    #import sys
    #sys.exit()

mazes, start, end, min = load("input_maze.txt")
search(mazes, start, end, min)