JOI 2011 予選 5 - チーズ を解きました！（BFS 幅優先探索）

問題はこちらです！拙いコードですがご意見などございましたらお願いします！

atcoder.jp

~
#!/usr/bin/env python3

import sys
from itertools import accumulate,permutations,combinations,product
from collections import deque,defaultdict,Counter
from math import factorial,gcd
from functools import reduce
from operator import add
from operator import sub
from operator import mul
from bisect import bisect_left,bisect_right
from heapq import heappop, heappush
from functools import lru_cache
import queue

def I(): return int(input())
#def I(): return input()
def LI(): return list(map(int,input().split()))

def _main():
    input = sys.stdin.readline
    sys.setrecursionlimit(int(1e+7))
    h,w,n = map(int,input().split())
    matrix = []
    factory = [[0,0],[0,0],[0,0],[0,0],[0,0],[0,0],[0,0],[0,0],[0,0]]
    for i in range(h):
        x = input()
        matrix.append(x)
        if 'S' in x:
            sy = i
            sx = x.index("S")
        if '1' in x:
            factory[0][0] = x.index('1')
            factory[0][1] = i 
        if '2' in x:
            factory[1][0] = x.index('2')
            factory[1][1] = i 
        if '3' in x:
            factory[2][0] = x.index('3')
            factory[2][1] = i 
        if '4' in x:
            factory[3][0] = x.index('4')
            factory[3][1] = i 
        if '5' in x:
            factory[4][0] = x.index('5')
            factory[4][1] = i 
        if '6' in x:
            factory[5][0] = x.index('6')
            factory[5][1] = i 
        if '7' in x:
            factory[6][0] = x.index('7')
            factory[6][1] = i
        if '8' in x:
            factory[7][0] = x.index('8')
            factory[7][1] = i 
        if '9' in x:
            factory[8][0] = x.index('9')
            factory[8][1] = i

    q = deque()
    dex,dey = factory[0][0],factory[0][1]
    visited = [[0]*w for _ in range(h)]
    q.append((sy,sx,0))
    ans =0
    dydx = ((1,0),(0,1),(-1,0),(0,-1))
    destinationindex = 0
    while q:
        y,x,d = q.popleft()

        if (y,x)==(dey,dex):
            ans+=d

            if y == factory[n-1][1] and x == factory[n-1][0]:
                break

            destinationindex += 1
            dex,dey = factory[destinationindex]
            q = deque()
            q.append((y,x,0))
            visited = [[0]*w for _ in range(h)]
            continue
        
        if visited[y][x]:
            continue
        else:
            visited[y][x] = 1
            for dy,dx in dydx:
                if 0<=y+dy<h and 0<=x+dx<w:
                    if matrix[y+dy][x+dx] != "X" and not visited[y+dy][x+dx]:
                        q.append((y+dy,x+dx,d+1))
    print(ans)

if __name__ == '__main__':
    _main()
~