続・3時間クッキング

　今度は空白だらけの地図でも迷わないよ。
　ネットの解答例をかなり読んでから再挑戦したため、僕の実力じゃあないんだけどさ。
　結局、アメーバのように全方位まんべんなくジワジワと探査して、探査をやり直すハメになったときの手間を減らす作戦をとった。重みとか関係ないからダイクストラ法とはいえないね。
　pythonまだ慣れないけど、なんかselfだらけになるなあコレ。そこだけは仕様としてしっくりこない。

# -*- coding: mbcs -*-

'''
迷路を記述されたファイルを受け取って、最短経路を記述したファイルを出力します

input:filepath of maze 
writefile 'result.txt' in directory of inputfile

@author: Keniya
'''
import os
import sys

SPACE = ' ';
BLOCK = '*';
START = 'S';
GOAL = 'G';
MOVED = '$';
MAZE_CHARSET = (SPACE,BLOCK,START,GOAL,MOVED)

class Maze:
    def __init__(self,filepath):
        self.mazeMap = []
        file = open(filepath)
        try:
            yidx = 0
            for line in file:
                mazeline = []
                xidx = 0;
                for char in line:
                    mazeCell = {'c':char, 'step':0, 'prev':None}
                    if char in MAZE_CHARSET:
                        mazeline.append(mazeCell)
                        if char == 'S': self.sPos = (yidx,xidx)
                        elif char == 'G': self.gPos = (yidx,xidx)
                    elif char != '\n':
                        raise 'UnexpectedChar',char
                    xidx += 1
                self.mazeMap.append(mazeline)
                yidx += 1
        finally:
            file.close()

    def __str__(self):
        s = '';
        for line in self.mazeMap:
            for cell in line: s += cell['c']
            s += '\n'
        return s

    def __canMove(self, y, x, cnt):
        #移動できる？
        try:
            status = self.mazeMap[y][x]['c']
            if (status != SPACE) and (status != GOAL): return False 
        except:
            return False
        #最小歩数到達ならOK!
        return (self.mazeMap[y][x]['step'] < 1) or (self.mazeMap[y][x]['step'] > cnt)

    def putResultFile(self,filepath):
        f = open(filepath + '\\result.txt','w')
        try:
            s = str(self)
            f.write(s)
        finally:
            f.close()

    def solve(self): 
        print self
        
        searching = True
        candidates = [self.sPos]
        while searching:
            for pos in candidates:
                y = pos[0]
                x = pos[1]
                cnt = self.mazeMap[y][x]['step']
                char = self.mazeMap[y][x]['c']
                for p in [(y,x+1),(y,x-1),(y+1,x),(y-1,x)]:
                    if self.__canMove(p[0], p[1], cnt+1):
                        candidates.append(p)
                        self.mazeMap[p[0]][p[1]]['step'] = cnt+1
                        self.mazeMap[p[0]][p[1]]['prev'] = pos
                candidates.remove(pos)
            if not candidates:
                candidates.__str__()
                break
        
        prev = self.gPos
        while True:
            char = self.mazeMap[prev[0]][prev[1]]['c']
            if char == START: break
            if char == SPACE: self.mazeMap[prev[0]][prev[1]]['c'] = MOVED
            prev = self.mazeMap[prev[0]][prev[1]]['prev']
        
        print "Step:",self.mazeMap[self.gPos[0]][self.gPos[1]]['step']
        print self
        
#----------------------------------------
# Main始まるよー
#----------------------------------------
if __name__ == "__main__":
    print 'start'
    import time
    t1 = time.time()
    
    #引数からファイルパス取得
    filepath = sys.argv[1]
    
    #解け！
    maze = Maze(filepath)
    maze.solve()
    maze.putResultFile(os.path.dirname(filepath))
    
    t2 = time.time()
    print (t2-t1)*1000,'ms'
    
    print 'end'