Express Delivery (DropBox) - 荷物の運搬

どんな問題？

Express Delivery
http://www.checkio.org/mission/express-delivery/

スタート地点からゴールまで荷物を運ぶ。
フィールドには、いくつかのBoxがあり、Boxに荷物を入れると、どのBoxからでも取り出すことができる。
1マスの移動には、荷物を持っているときは2分、荷物を持っていないときは1分かかる。Boxに荷物を積み込むときと、取り出すときにも1分かかる。
このとき、最短時間で荷物をゴールまで運ぶためのルートを見つけよ。

荷物はBox間をワープできるが、自分はワープできないので歩いていく必要がある。

引数は、フィールドデータが文字列のリストで渡される。

W	水（通行不可）
B	Box
E	ゴール
S	スタート
.	空き

戻り値は、ルートを文字列で返す。

U	上へ（北）
D	下へ（南）
L	左へ（西）
R	右へ（東）
B	箱に積み込む/取り出す

例題：

checkio(["S...","....","B.WB","..WE"]) == "RRRDDD"
checkio(["S...","....","B..B","..WE"]) == "DDBRRRBD"

フィールドのサイズは、縦・横ともに10未満。

どうやって解く？

先日苦労した Haunted House の解き方が役に立ちそうだ。グラフの頂点（ノード）とは、オセロの盤面のような「状態」として考えればいい。となると、今回の問題では、自分の位置＋荷物を持っているかどうか、の2つを頂点とすればいいんじゃないだろうか？

あとは重み付きグラフの最短経路問題なので、Bats Bunker のようにダイクストラ法を使えばいいかな。ダイクストラ法では、ヒープキューを使って、スタートからの時間を優先度とするんだっけ。

最初に、フィールドデータを、(x,y)をキーとする辞書に変換している。

map_data = {(x, y): c for y, line in enumerate(field_map) for x, c in enumerate(line)}

get_next()関数では、隣の頂点（ノード）を列挙する。自分の上下左右のマスを調べて、Boxであれば、移動して荷物を積み込む/取り出す場合と、移動するだけの2パターンがある。Box以外なら移動するだけ。移動時間は、自分が荷物を持っているかどうかで変わるので注意。

def get_next(n, c):
    for act in 'LRUD':
        d = MOVE[act]
        pt = n[0] + d[0], n[1] + d[1]
        if pt not in map_data or map_data[pt] == 'W':
            continue
        m = 2 if c else 1
        if map_data[pt] == 'B':  # box
            yield act + 'B', m + 1, pt, not c  # +1 for load/unload
        yield act, m, pt, c

荷物を持った状態でゴールに着けば終了だ。

まとめ

import heapq

MOVE = {'L': (-1, 0), 'R': (1, 0), 'U': (0, -1), 'D': (0, 1)}  # (x,y)

def checkio(field_map):
    def get_next(n, c):
        for act in 'LRUD':
            d = MOVE[act]
            pt = n[0] + d[0], n[1] + d[1]
            if pt not in map_data or map_data[pt] == 'W':
                continue
            m = 2 if c else 1
            if map_data[pt] == 'B':  # box
                yield act + 'B', m + 1, pt, not c  # +1 for load/unload
            yield act, m, pt, c

    map_data = {(x, y): c for y, line in enumerate(field_map) for x, c in enumerate(line)}
    start = [k for k, v in map_data.items() if v == 'S'][0]
    seen = set()
    heap = [(0, start, True, '')]  # list of (total_time, nicola, with_cargo, route)
    while heap:
        time, nicola, cargo, route = heapq.heappop(heap)
        seen.add((nicola, cargo))
        if cargo and map_data[nicola] == 'E':
            return route
        for action, minutes, new_nicola, new_cargo in get_next(nicola, cargo):
            if (new_nicola, new_cargo) in seen:
                continue
            new_time = time + minutes
            new_route = route + action
            heapq.heappush(heap, (new_time, new_nicola, new_cargo, new_route))

http://www.checkio.org/mission/express-delivery/

他の人の答え

また後日。