Hypyt

def preProc(grid): # se edelinen bfs ratkasu oli liia vitun hidas, TAAS PERKELE, MÄ TULEN HULLUKSI JOS MUN PITÄÄ TEHÄ TÄÄ ROSKA EES VIELÄ KERRAN ALUST ASTI. Joten, FUCK IT preprocessoidaan KOKO PASKA
    y, x = len(grid), len(grid[0])
    n = y+x
    adj = []
    for _ in range(n):
        adj.append([])

    for r in range(y):
        for c in range(x):
            if grid[r][c] == '.':
                adj[r].append(y+c)
                adj[y+c].append(r)

    dist = []
    for _ in range(n):
        dist.append([-1]*n)
    
    for star in range(n):
        q = [star]
        h = 0
        dist[star][star] = 0

        while h < len(q):
            u =q[h]
            h += 1
            for v in adj[u]:
                if dist[star][v] == -1:
                    dist[star][v] = dist[star][u] + 1
                    q.append(v)

    return dist, y, x



def shortestPath(dist, y, x, sy, sx, ey, ex):
    sy -= 1
    sx -= 1
    ey -= 1
    ex -= 1

    if sy == ey and sx == ex:
        return 0
    if sy == ey and grid[sy][sx] == '.' and grid [ey][ex] == '.':
        return 1
    if sx == ex and grid[sy][sx] == '.' and grid [ey][ex] == '.':
        return 1
    rowS, colS = sy, y+sx
    rowE, colE = ey, y+ex

    res = float('inf')
    for a in (rowS, colS):
        for b in (rowE, colE):
            d = dist[a][b]
            if d != -1 and d < res:
                res = d
    if res == float('inf'):
        return -1
    return res +1 if res > 0 else 0



y, x, q = map(int, input().split())
grid = []
for i in range(y):
    row = []
    inp = input()
    for a in range(x):
        row.append(inp[a])
    grid.append(row)
quests = []
for _ in range(q):
    sy, sx, ey, ex = map(int, input().split())
    star = sy, sx
    end = ey, ex
    quests.append(star)
    quests.append(end)

dist, y, x = preProc(grid)

for n in range(len(quests)):
    if(n % 2) == 0:
        sy, sx = quests[n]
        ey, ex = quests[n+1]
        print(shortestPath(dist, y, x, sy, sx, ey, ex))

Test 1 (public)

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

Test 2

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

Test 3

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

Test 4

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

Test 5

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

Test 6

Group: 2, 5

Verdict: ACCEPTED

Test 7

Group: 2, 5

Verdict: ACCEPTED

Test 8

Group: 2, 5

Verdict: ACCEPTED

Test 9

Group: 3, 4, 5

Verdict: ACCEPTED

Test 10

Group: 3, 4, 5

Verdict: ACCEPTED

Test 11

Group: 3, 4, 5

Verdict: ACCEPTED

Test 12

Group: 4, 5

Verdict: ACCEPTED

Test 13

Group: 4, 5

Verdict: ACCEPTED

Test 14

Group: 4, 5

Verdict: ACCEPTED

Test 15

Group: 5

Verdict: ACCEPTED

Test 16

Group: 5

Verdict: ACCEPTED

Test 17

Group: 5

Verdict: ACCEPTED

Test 18

Group: 5

Verdict: ACCEPTED

Test 19

Group: 5

Verdict: ACCEPTED

Test 20

Group: 5

Verdict: ACCEPTED

Test 21

Group: 5

Verdict: ACCEPTED

Test 22

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

Test 23

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

Test 24

Group: 5

Verdict: ACCEPTED

Test 25

Group: 5

Verdict: ACCEPTED

Test 26

Group: 5

Verdict: ACCEPTED

Test 27

Group: 5

Verdict: ACCEPTED