「人材獲得作戦・４　試験問題ほか」を解いてみた。
前回の続きです。

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

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

次に考えた方法は、スタート地点から各方向へ一歩ずつ進んでいきます。
このとき、通った道は記録しておきます。
既に通った道は二度と通らないようにするため、壁にしてしまいます。
一番最初にゴール地点に到着したときの道が最短経路になります。

イメージとしては、こんな感じです。

プログラムの流れは次のようになります。

def main():
    # 地図の読み込み
    map = load_map()
    # スタート地点の座標を取得する
    start = parse_pos(map)
    # スタート地点から一歩ずつ調べる
    route = search(copy.deepcopy(map), [(start[0], start[1], [])])
    # 答えを出力する
    print_answer(map, route)

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

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

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

スタート地点から一歩ずつ調べる処理です。
移動できる座標が見つかれば、次回の探索開始位置として記録します。
ゴールが見つかるまで、探索を繰り返します。
ゴールが見つかったら、今までたどってきた経路を返します。

def search(map, pos_list):
    """
    スタート地点から一歩ずつ調べる
    map 探索用の地図
    pos_list 探索する座標とその座標にたどり着いた経路
    """
    next_pos_list = [] # 次の歩で探索を開始する座標のリスト
    for y,x,route 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] == "G": 
                route.append((y,x))
                return route
            # 移動できる座標が見つかった
            if map[pos_y][pos_x] == " ":
                new_route = route[:]
                new_route.append((y,x))
                next_pos_list.append((pos_y, pos_x, new_route))
                map[pos_y][pos_x] = "*" #探索済み
    assert len(next_pos_list) > 0, "Goal is not found."
    return search(map, next_pos_list)

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

def print_answer(map, route):
    """答えを出力する"""
    for y in range(len(map)):
        for x in range(len(map[y])):
            if (map[y][x] == "S") or (map[y][x] == "G"):
                sys.stdout.write(map[y][x])
            elif (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)
    # スタート地点から一歩ずつ調べる
    route = search(copy.deepcopy(map), [(start[0], start[1], [])])
    # 答えを出力する
    print_answer(map, route)

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

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

def search(map, pos_list):
    """
    スタート地点から一歩ずつ調べる
    map 探索用の地図
    pos_list 探索する座標とその座標にたどり着いた経路
    """
    next_pos_list = []
    for y,x,route 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] == "G": 
                route.append((y,x))
                return route
            if map[pos_y][pos_x] == " ":
                new_route = route[:]
                new_route.append((y,x))
                next_pos_list.append((pos_y, pos_x, new_route))
                map[pos_y][pos_x] = "*" #探索済み
    assert len(next_pos_list) > 0, "Goal is not found."
    return search(map, next_pos_list)

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

        print

if __name__ == "__main__":
    main()