Submission #2485535

---

Source Code Expand

from heapq import heappush, heappop
R, C = map(int, input().split())
sx = sy = tx = ty = 0
M = []
for i in range(R):
    A = input()
    tmp = []
    for j, a in enumerate(A):
        if a == 's':
            sx = j; sy = i
            tmp.append(0)
        elif a == 't':
            tx = j; ty = i
            tmp.append(0)
        else:
            tmp.append(int(a))
    M.append(tmp)

d = [1, -1, -1, 0, 1, 1, 0, -1, 1]
*dd, = zip(d, d[1:])

que = [(0, sx, sy)]
dist = [[10**9]*C for i in range(R)]
dist[sy][sx] = 0
while que:
    cost, x, y = heappop(que)
    if dist[y][x] < cost:
        continue
    for dx, dy in dd:
        nx = x + dx; ny = y + dy
        if not 0 <= nx < C or not 0 <= ny < R:
            continue
        c = M[ny][nx]
        if cost + c < dist[ny][nx]:
            dist[ny][nx] = cost + c
            heappush(que, (cost + c, nx, ny))
print(dist[ty][tx])

Submission Info

Judge Result