「人材獲得作戦・４　試験問題ほか」を解いてみた。

問題
壁とスペースで構成された迷路が与えられたとき、スタート地点からゴール地点に至る最短経路を求めよ

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

最初に思いついた方法はスタート地点から各地点への距離を求めて、ゴール地点から最短距離をたどるという方法です。

import sys, copy

def main():
    # 地図の読み込み
    map = load_map()
    # スタート地点とゴール地点の座標を取得する
    start = parse_pos(map, "S")
    goal = parse_pos(map, "G")
    # スタート地点から各座標への距離を求める
    distance_map = measure_distance(copy.deepcopy(map), [start], 1)
    # ゴール地点から最短距離をたどってスタート地点に行く
    route = examine_route(distance_map, goal, [])
    # 答えを出力する
    print_answer(map, route)

まず最初に問題を解くのに必要な情報を取得します。

def load_map():
    """地図を読み込む"""
    map = []
    for line in sys.stdin:
        map.append(list(line.strip()))
    return map

def parse_pos(map, p):
    """スタート地点の座標を取得する"""
    for y in range(len(map)):
        for x in range(len(map[y])):
            if map[y][x] == p: return (y, x)
    raise Exception, '%s is not found.' % p

スタート地点から一マスずつ距離を地図に記載していきます。

def measure_distance(map, pos_list, dist):
    """
    スタート地点から各座標への距離を求める
    map 地図
    pos_list 探索開始地点
    dist 距離
    """
    next_pos_list = []
    for y,x in pos_list:
        for pos_y,pos_x in [(y,x+1),(y,x-1),(y+1,x),(y-1,x)]:
            if map[pos_y][pos_x] == ' ':
                map[pos_y][pos_x] = dist
                next_pos_list.append((pos_y,pos_x))
    if len(next_pos_list) == 0: return map
    return measure_distance(map, next_pos_list, dist+1)

次のような地図ができました。

 *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *
 *  S  *  8  * 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29  *
 *  1  *  7  *  9 10  * 14 15  *  *  *  *  *  *  *  *  *  *  *  *  * 29 30  *
 *  2  *  6  7  8  * 16 15 16 17  *  *  *  *  *  *  *  *  *  *  *  * 30 31  *
 *  3  4  5  6  * 18 17 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32  *
 *  *  *  *  *  *  *  *  *  *  *  *  *  * 23  *  *  *  *  *  *  *  *  *  *  *
 * 37 36 35 34 33 32 31 30 29 28 27 26 25 24 25 26 27 28 29 30 31 32 33 34  *
 *  * 37  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *
 * 39 38 39 40 41 42  * 46 47 48 49 50 51 52 53 54 55 56 57 58 59  G 65 66  *
 * 40 39  * 41 42 43 44 45 46  *  *  *  *  *  *  *  *  *  *  * 60  * 64 65  *
 * 41 40 41 42  * 44 45 46 47 48 49 50 51  *  *  *  *  *  *  * 61  * 63 64  *
 * 42 41 42 43 44 45 46  * 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63  *
 *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *

次にゴール地点Gから上下左右の座標を調べて、もっとも距離の小さい座標を見つけます。
見つかったらその座標を記録して、次にその座標からもっとも距離の小さい座標を見つけます。
以下、スタート地点が見つかるまで繰り返します。
スタート地点が見つかったら、今までたどってきた座標を返します。

def examine_route(map, goal, route):
    """
    ゴール地点から最短距離をたどってスタート地点に行く
    distance_map スタート地点からの距離を記載した地図
    goal 検索開始地点の座標
    """
    y,x = goal
    next_pos = None
    dist = len(map) * len(map[0])
    for pos_y,pos_x in [(y,x+1),(y,x-1),(y+1,x),(y-1,x)]:
        cell = map[pos_y][pos_x]
        if cell == 'S': return route
        elif cell == "*": continue
        elif cell < dist:
            dist = cell
            next_pos = (pos_y, pos_x)
    route.append(next_pos)
    return examine_route(map, next_pos, route)

最短経路が見つかったので、出力します。

def print_answer(map, route):
    """答えを出力する"""
    for y in range(len(map)):
        for x in range(len(map[y])):
            if (y,x) in route:
                sys.stdout.write("$")
            else:
                sys.stdout.write(map[y][x])
        print

ソースコードの全体は次のようになります。

#python
# -*- coding: shift-jis -*-
import sys, copy

def main():
    # 地図の読み込み
    map = load_map()
    # スタート地点とゴール地点の座標を取得する
    start = parse_pos(map, "S")
    goal = parse_pos(map, "G")
    # スタート地点から各座標への距離を求める
    distance_map = measure_distance(copy.deepcopy(map), [start], 1)
    # ゴール地点から最短距離をたどってスタート地点に行く
    route = examine_route(distance_map, goal, [])
    # 答えを出力する
    print_answer(map, route)

def load_map():
    """地図を読み込む"""
    map = []
    for line in sys.stdin:
        map.append(list(line.strip()))
    return map

def parse_pos(map, p):
    """座標を取得する"""
    for y in range(len(map)):
        for x in range(len(map[y])):
            if map[y][x] == p: return (y, x)
    raise Exception, '%s is not found.' % p

def measure_distance(map, pos_list, dist):
    """
    スタート地点から各座標への距離を求める
    map 地図
    pos_list 探索開始地点
    dist 距離
    """
    next_pos_list = []
    for y,x in pos_list:
        for pos_y,pos_x in [(y,x+1),(y,x-1),(y+1,x),(y-1,x)]:
            if map[pos_y][pos_x] == ' ':
                map[pos_y][pos_x] = dist
                next_pos_list.append((pos_y,pos_x))
    if len(next_pos_list) == 0: return map
    return measure_distance(map, next_pos_list, dist+1)

def examine_route(map, goal, route):
    """
    ゴール地点から最短距離をたどってスタート地点に行く
    distance_map スタート地点からの距離を記載した地図
    goal 検索開始地点の座標
    """
    y,x = goal
    next_pos = None
    dist = len(map) * len(map[0])
    for pos_y,pos_x in [(y,x+1),(y,x-1),(y+1,x),(y-1,x)]:
        cell = map[pos_y][pos_x]
        if cell == 'S': return route
        elif cell == "*": continue
        elif cell < dist:
            dist = cell
            next_pos = (pos_y, pos_x)
    route.append(next_pos)
    assert next_pos != None
    return examine_route(map, next_pos, route)

def print_answer(map, route):
    """答えを出力する"""
    for y in range(len(map)):
        for x in range(len(map[y])):
            if (y,x) in route:
                sys.stdout.write("$")
            else:
                sys.stdout.write(map[y][x])
        print

if __name__ == "__main__":
    main()