Hypyt

y, x, questions = input().split()

y = int(y)
x = int(x)
questions = int(questions)

area = []
safe = []

for i in range(y):
    area.append(list(input()))
    
for i in range(y):
    for j in range(x):
        if area[i][j] == ".":
            safe.append([i,j])

for i in range(questions):
    y1,x1,y2,x2 = input().split()
    y1 = int(y1)-1
    x1 = int(x1)-1
    y2 = int(y2)-1
    x2 = int(x2)-1

    jumps = 1

    paths = {"0 0": 0}

    using_paths = []

    not_possible = False

    cur_pos = [y1,x1]
    target_pos = [y2, x2]

    current_paths = [cur_pos]

    if cur_pos != target_pos:
        while not str(target_pos) in paths:
            using_paths = current_paths.copy()

            possible_path = []

            for path in using_paths:
                for pos in safe:
                    if pos != path:
                        if not str(pos) in paths:
                            if path[0] == pos[0] or path[1] == pos[1]:
                                possible_path.append(pos)

            if len(possible_path) != 0:
                for path in possible_path:
                    paths.update({str(path): jumps})
                    current_paths.append(path)
            else:
                not_possible = True
                break
            
            if str(target_pos) in paths:
                break

            for path in using_paths:
                current_paths.remove(path)
            jumps += 1

        if (not_possible):
            print(-1)
        else:
            print(paths[str(target_pos)])
    else:
        print(0)
    

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: TIME LIMIT EXCEEDED

Test 7

Group: 2, 5

Verdict: TIME LIMIT EXCEEDED

Test 8

Group: 2, 5

Verdict: TIME LIMIT EXCEEDED

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: TIME LIMIT EXCEEDED

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: ACCEPTED

Test 23

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

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