迷路問題

人生を書き換える者すらいた。: 人材獲得作戦・４　試験問題ほか
を解いてみました。

迷路の最短経路を捜す問題です。

**************************
*S* *                    *
* * *  *  *************  *
* *   *    ************  *
*    *                   *
************** ***********
*                        *
** ***********************
*      *              G  *
*  *      *********** *  *
*    *        ******* *  *
*       *                *
**************************

解くだけはダイクストラ法（だと思う）で30分ほどで出来ました。

全ての最短経路を出力します。

周りの数字はデバッグ用の名残です。

試験問題には、経路の最短性もチェックしろという事だったのですが、
逆にチェックする方が難しいような・・・って、いうか、最短性は明らか・・・？

#encoding:shift-jis
from __future__ import division, with_statement, print_function
from myutil import *

Meiro = namedtuple("Meiro", "map width height start goal")
"""
Meiro.map[x, y] == True if (x, y)の位置が壁
"""

def open_meiro(filename):
    with open(filename) as fp:
        lines = [line.rstrip() for line in fp]
        while not lines[-1]:
            lines.pop(-1)
    
    w = max(len(line) for line in lines)
    h = len(lines)
    
    m = {}
    start = goal = None
    for x, y in product(xrange(w), xrange(h)):
        m[x, y] = False
        if len(lines[y]) <= x:continue
        if lines[y][x] == "*":
            m[x, y] = True
        elif lines[y][x] == "S":
            assert start is None, "there is multiple S"
            start = (x, y)
        elif lines[y][x] == "G":
            assert goal is None, "there is multiple G"
            goal = (x, y)
    
    assert start, "there is not S"
    assert goal, "there is not G"
    
    return Meiro(m, w, h, start, goal)

def paths(meiro):
    paths = [[meiro.start]]
    visited = set([meiro.start])
    i = 0
    while True:
        paths1 = []
        i += 1
        for path in paths:
            tailx, taily = path[-1]
            for dx, dy in [(1, 0), (-1, 0), (0, -1), (0, 1)]:
                x = tailx + dx
                y = taily + dy
                if (x, y) not in meiro.map:
                    continue
                
                if not meiro.map[x, y] and (x, y) not in visited:
                    paths1.append(path + [(x, y)])
        
        paths = paths1
        visited = set(xy for path in paths for xy in path)
        if meiro.goal in visited:
            return [p for p in paths if p[-1] == meiro.goal]

def main():
    meiro = open_meiro("meiro.txt")
    ps = paths(meiro)
    
    def p(x):print(x, end="")
    for path in ps:
        p(" ")
        for x in xrange(meiro.width):
            p(str(x % 10))
        print()
        
        for y in xrange(meiro.height):
            p(str(y % 10))
            for x in xrange(meiro.width):
                if meiro.map[x, y]:
                    p("*")
                elif meiro.start == (x, y):
                    p("S")
                elif meiro.goal == (x, y):
                    p("G")
                elif (x, y) in path:
                    p("$")
                else:
                    p(" ")
            print()
    
if __name__ == "__main__":
    main()