SWEA - 1249. 보급로

for tc in range(1, 1 + int(input())):
    n = int(input())
    m = [list(map(int, input())) for _ in range(n)]
    v = [[9 * n * n] * n for _ in range(n)]
    v[0][0] = 0
    st = [(0, 0)]
    while st:
        st2 = []
        for r, c in st:
            for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                if 0 <= r + dr < n and 0 <= c + dc < n and v[r + dr][c + dc] > v[r][c] + m[r + dr][c + dc]:
                    v[r + dr][c + dc] = v[r][c] + m[r + dr][c + dc]
                    st2.append((r + dr, c + dc))
        st = st2
    print(f'#{tc}', v[n - 1][n - 1])