迷路問題（人材獲得作戦・４）を解いてみる

人材獲得作戦・４　試験問題ほか の問題を解いてみた。今日は 13 日、もうすでにいろんな人が解き終わっていて、反応鈍かった感は否めない。

所要時間 40 分だった。最短経路に $ を書き込まなければならないので、ある地点へ「到達できたこと」に加えて「到達する前にいた地点」も保持するようにした。

改良するならば、データ保持の方法からかな。通過点を保持する visited は辞書（ハッシュ）である必要はなくリストで十分。

迷路の保持方法もリストのリストでなく、単なるリストで十分。メモリをさらにケチるなら、迷路の要素が通路、壁だけと限られていることを利用して一要素 1 byte の配列で表現、つまり array.array('b') などにする。さらにケチって 1 ビットに詰め込むのも不可能ではないが、 Python つかっておいてそれはやりすぎか。

# coding: utf-8

from collections import deque

def solve_maze(maze):
    u"""迷路の最短経路を求める

    迷路はテキストで表されているものとする。それぞれの意味は
        ' ' 通路
        '*' 壁
        'S' スタート
        'G' ゴール
    である。

    たとえば、次のようなものである。

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

    答えもテキストで表される。通過点は $ で示す。
    
    **************************
    *S* *$$$$                *
    *$* *$ *$ *************  *
    *$*$$$* $  ************  *
    *$$$ *  $$$$$$$          *
    **************$***********
    * $$$$$$$$$$$$$          *
    **$***********************
    * $$$  *$$$$$$$$$$$$$$G  *
    *  *$$$$$ *********** *  *
    *    *        ******* *  *
    *       *                *
    **************************

    ゴールにたどり着けない場合、 None を返す。

    迷路の外周が長方形となっていない、
    スタートやゴールがない、複数ある、別の文字が含まれているなどの
    入力は想定していなく、正しく動作しない。
    """

    course = []
    for i, line in enumerate(maze.splitlines()):
        line = line.rstrip('\n')
        s = line.find('S')
        if s >= 0:
            start = (s, i)
        g = line.find('G')
        if g >= 0:
            goal = (g, i)
        course.append(list(line))

    cols = len(course[0])
    rows = len(course)

    visited = {start: None}
    queue = deque([start])
    i = 0
    while queue:
        if goal in visited:
            break
        for _ in xrange(len(queue)):
            pos = queue.popleft()
            for p in ((0, 1), (0, -1), (-1, 0), (1, 0)):
                new_pos = (pos[0] + p[0], pos[1] + p[1])
                if not (0 <= new_pos[0] < cols):
                    continue
                if not (0 <= new_pos[1] < rows):
                    continue
                if course[new_pos[1]][new_pos[0]] != '*':
                    if new_pos not in visited:
                        visited[new_pos] = pos
                        queue.append(new_pos)
                        if new_pos == goal:
                            break
            if goal in visited:
                break
        i += 1
    else:
        # ゴールにたどり着けなかった
        return None

    pos = goal
    while True:
        pos = visited[pos]
        if pos == start:
            break
        course[pos[1]][pos[0]] = '$'

    answer = []
    for line in course:
        answer.append(''.join(line))
        answer.append('\n')

    return ''.join(answer)

def main():
    import sys
    input = sys.stdin.read()
    output = solve_maze(input)
    if output:
        sys.stdout.write(output)
    else:
        sys.stdout.write('no answer.')

if __name__ == '__main__':
    main()

追記。 Windows 上の Python （自分もなのだけれども）でこれを動かす時には spam.py < input.txt のようなコマンドでは動かない。 python spam.py < input.txt とする必要がある。標準入力の使用に一癖あるようだ。