JOI 2010 予選 E チーズ - いろんなことで四苦Hack（仮）

の続きです。

BFSの続き。迷路には、'X'と'.'と1~9までの数字が埋まっており、スタートからマスを進んで、1~9を順番に取っていき、その時の最小手数を求めてねという問題。

from collections import deque
BIG = 1000000


def main():
    h, w, k = [int(i) for i in input().split()]
    f = []
    for i in range(h):
        line = list(input())
        for j, c in enumerate(line):
            if c == 'S':
                sy, sx = [i, j]
        f.append(line)

    turn = [[[BIG, 0] for i in range(w)] for j in range(h)]
    turn[sy][sx][0] = 0
    turn[sy][sx][1] = 1
    q = deque([[sy, sx]])
    # 探してる数
    c = 1
    y, x = (0, 0)

    while q:
        y, x = q.pop()
        if f[y][x] == str(c):
            c += 1
            if c > k:
                break
            q.clear()
        for dy, dx in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            ny, nx = y+dy, x+dx
            if 0 <= ny < h and 0 <= nx < w and \
                f[ny][nx] != 'X' and turn[ny][nx][1] < c:
                # 訪れたとこを記録していない
                turn[y+dy][x+dx][0] = turn[y][x][0] + 1
                turn[y+dy][x+dx][1] = c
                q.appendleft([ny, nx])
    print(turn[y][x][0])

if __name__ == '__main__':
    main()

手数と、c (探している番号) で通ったかをメモりながら、進んでいく。1 s はかからなかったけど、0.8 msぐらいかかってて遅いなと思った。オリジナルの地図に書き込んで進もうと思ったんだけど、なかなかうまくいかなかった。なので、諦めて 2 個組を要素にもつ地図をコピーしてやった。思ってたより実装に時間がかかったり、既に行ったかどうかが抜けてたりして、時間がかかってしまった。