ALDS1_13_C: 15 Puzzle (続き5 A*)

A*にとりかかるまえにちょっと試す

履歴をsetに覚えさせるあたりが重かった？

幅優先探索＋マンハッタン距離の差分計算バージョンから
履歴を覚えてチェックするところを省いてみた
12番(15手)で比べてみると
チェックあり： 01.59s、チェックなし: TLE(16秒以上)
ループどころか行って戻るのチェックもないし仕方ないな
これだけだとなんも言えんね

ではA*のサンプルを参考に
そんなに書き替え箇所は多くなかった
幅優先とはdequeを使うかheapqを使うかくらいしか変わってない感じ

heapqをsolveの中でimportしてるのはその方が速いかなということで

class State:
    def __lt__(self, other):
        return self.c + self.d < other.c + other.d

def solve(init):
    from heapq import heappush, heappop

    hist = set()
    q = []
    heappush(q, init)
    while len(q) > 0:
        s = heappop(q)
        if s.d == 0:
            return s.c

        t = tuple(s.b)
        if t not in hist and s.d + s.c <= 45:
            hist.add(t)
            for h in [-1, 1, -4, 4]:
                c = s.z % 4
                r = s.z // 4
                if (
                    (c == 0 and h == -1)
                    or (c == 3 and h == 1)
                    or (r == 0 and h == -4)
                    or (r == 3 and h == 4)
                ):
                    continue

                ns = s.dup()
                ns.z += h
                ns.d -= State.MDT[ns.z][ns.b[ns.z] - 1]
                ns.d += State.MDT[s.z][ns.b[ns.z] - 1]
                ns.b[s.z], ns.b[ns.z] = ns.b[ns.z], ns.b[s.z]
                ns.c += 1

                heappush(q, ns)

25番(44手)でTLE ローカル計測では20.944s
26番以降もローカルでは正解出してるしこれもこれくらいでいいか

さてこれが最後の問題だったわけだが
どれだか忘れたけどあとでやる、と思ってたのがあったはずなんだよな
どれだったかな