보급로 - SWEA

보급로

from collections import deque

dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]

T = int(input())

for test_case in range(1, T + 1):
    N = int(input())
    board = [list(map(int, input())) for _ in range(N)]
    visit = [[-1] * N for _ in range(N)]
    q = deque()
    q.append((0, 0))
    visit[0][0] = board[0][0]

    while q:
        y, x = q.popleft()
        if y == N - 1 and x == N - 1:
            continue
        cur = visit[y][x]
        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]
            if nx < 0 or ny < 0 or nx >= N or ny >= N:
                continue
            if visit[ny][nx] == -1 or cur + board[ny][nx] < visit[ny][nx]:
                visit[ny][nx] = cur + board[ny][nx]
                q.append((ny, nx))
    print("#" + str(test_case) + " " + str(visit[N-1][N-1]))