Submission #54864699

---

Source Code Expand

from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix

H, W, T = map(int, input().split())
S = [input() for _ in range(H)]


def canArrive(x):
    length, frm, to = [], [], []

    def path_append(fh, fw, th, tw):
        if S[th][tw] == '#':
            length.append(x)
        else:
            length.append(1)
        frm.append(fh * W + fw)
        to.append(th * W + tw)

    for h in range(H):
        for w in range(W - 1):
            path_append(h, w, h, w + 1)
            path_append(h, w + 1, h, w)
    for h in range(H - 1):
        for w in range(W):
            path_append(h, w, h + 1, w)
            path_append(h + 1, w, h, w)

    for h in range(H):
        for w in range(W):
            if S[h][w] == 'S':
                start = h * W + w
            elif S[h][w] == 'G':
                goal = h * W + w

    matr = csr_matrix((length, (frm, to)), shape=(H * W, H * W))
    return int(dijkstra(matr, indices=start)[goal]) <= T


l, r = 1, 10 ** 9
while r - l > 1:
    m = (l + r) // 2
    if canArrive(m):
        l = m
    else:
        r = m
print(l)

Submission Info

Judge Result