Hypyt

from collections import deque
import sys
input = sys.stdin.readline

n, m, q = map(int, input().split())
grid = [input().strip() for _ in range(n)]

# Indeksoidaan ruudut lineaarisesti: id = i*m + j
NM = n * m

# 1) Rivijaksot ja niiden ruutulistat
row_comp = [[-1] * m for _ in range(n)]
row_cells = []  # list of lists
r_id = 0
for i in range(n):
    j = 0
    while j < m:
        if grid[i][j] == '*':
            j += 1
            continue
        cells = []
        while j < m and grid[i][j] == '.':
            row_comp[i][j] = r_id
            cells.append(i * m + j)
            j += 1
        row_cells.append(cells)
        r_id += 1

# 2) Sarakejaksot ja niiden ruutulistat
col_comp = [[-1] * m for _ in range(n)]
col_cells = []
c_id = 0
for j in range(m):
    i = 0
    while i < n:
        if grid[i][j] == '*':
            i += 1
            continue
        cells = []
        while i < n and grid[i][j] == '.':
            col_comp[i][j] = c_id
            cells.append(i * m + j)
            i += 1
        col_cells.append(cells)
        c_id += 1

# apurakenteet: map ruutu -> (row_id, col_id)
cell_row = [-1] * NM
cell_col = [-1] * NM
for i in range(n):
    for j in range(m):
        if grid[i][j] == '.':
            idx = i * m + j
            cell_row[idx] = row_comp[i][j]
            cell_col[idx] = col_comp[i][j]

# visited -taulut timestamp-menetelmällä
vis_cell = [0] * NM
vis_row = [0] * r_id
vis_col = [0] * c_id
dist = [-1] * NM
cur_stamp = 1

out_lines = []
for _ in range(q):
    y1, x1, y2, x2 = map(int, input().split())
    y1 -= 1; x1 -= 1; y2 -= 1; x2 -= 1
    s_idx = y1 * m + x1
    t_idx = y2 * m + x2

    # jos jompikumpi on hirviö (tehtävä sanoo, etteivät ole), suoraan -1
    if grid[y1][x1] == '*' or grid[y2][x2] == '*':
        out_lines.append("-1")
        continue

    if s_idx == t_idx:
        out_lines.append("0")
        continue

    # BFS, mutta jokainen rivijakso/sarakejakso käsitellään vähintään kerran
    qd = deque()
    stamp = cur_stamp
    cur_stamp += 1
    # alustus start
    vis_cell[s_idx] = stamp
    dist[s_idx] = 0
    qd.append(s_idx)

    found = -1
    while qd:
        u = qd.popleft()
        d = dist[u]
        # laajennus rivijaksoon
        r = cell_row[u]
        if r != -1 and vis_row[r] != stamp:
            vis_row[r] = stamp
            for v in row_cells[r]:
                if vis_cell[v] != stamp:
                    vis_cell[v] = stamp
                    dist[v] = d + 1
                    if v == t_idx:
                        found = dist[v]
                        qd.clear()
                        break
                    qd.append(v)
            if found != -1:
                break
        # laajennus sarakejaksoon
        c = cell_col[u]
        if c != -1 and vis_col[c] != stamp:
            vis_col[c] = stamp
            for v in col_cells[c]:
                if vis_cell[v] != stamp:
                    vis_cell[v] = stamp
                    dist[v] = d + 1
                    if v == t_idx:
                        found = dist[v]
                        qd.clear()
                        break
                    qd.append(v)
            if found != -1:
                break

    if found == -1:
        out_lines.append("-1")
    else:
        out_lines.append(str(found))

# tulosta kaikki
print("\n".join(out_lines))

Test 1 (public)

Group: 1, 2, 3, 4, 5

Verdict: WRONG ANSWER

Test 2

Group: 1, 2, 3, 4, 5

Verdict: WRONG ANSWER

Test 3

Group: 1, 2, 3, 4, 5

Verdict: WRONG ANSWER

Test 4

Group: 1, 2, 3, 4, 5

Verdict: WRONG ANSWER

Test 5

Group: 1, 2, 3, 4, 5

Verdict: WRONG ANSWER

Test 6

Group: 2, 5

Verdict: TIME LIMIT EXCEEDED

Test 7

Group: 2, 5

Verdict: WRONG ANSWER

Test 8

Group: 2, 5

Verdict: WRONG ANSWER

Test 9

Group: 3, 4, 5

Verdict: TIME LIMIT EXCEEDED

Test 10

Group: 3, 4, 5

Verdict: TIME LIMIT EXCEEDED

Test 11

Group: 3, 4, 5

Verdict: TIME LIMIT EXCEEDED

Test 12

Group: 4, 5

Verdict: TIME LIMIT EXCEEDED

Test 13

Group: 4, 5

Verdict: TIME LIMIT EXCEEDED

Test 14

Group: 4, 5

Verdict: TIME LIMIT EXCEEDED

Test 15

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 16

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 17

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 18

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 19

Group: 5

Verdict: WRONG ANSWER

Test 20

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 21

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 22

Group: 1, 2, 3, 4, 5

Verdict: WRONG ANSWER

Test 23

Group: 1, 2, 3, 4, 5

Verdict: WRONG ANSWER

Test 24

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 25

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 26

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 27

Group: 5

Verdict: ACCEPTED