Hypyt

import java.util.*;


public class jumps {

	static List<List<Integer>> r_safespaces = new ArrayList<>();
	static List<List<Integer>> c_safespaces = new ArrayList<>();

    public static void main(String[] args) {
        	Scanner sc = new Scanner(System.in);
        	int n = sc.nextInt();
        	int m = sc.nextInt();
        	int q = sc.nextInt();
		sc.nextLine();

        	String[] grid = new String[n];
        	for (int i = 0; i < n; i++) {
            		grid[i] = sc.nextLine().trim();
        	}
        

        	int[][] queries = new int[q][4];
        	for (int i = 0; i < q; i++) {
            		queries[i][0] = sc.nextInt();
            		queries[i][1] = sc.nextInt();
            		queries[i][2] = sc.nextInt();
			queries[i][3] = sc.nextInt();
		}
        

		for (int i = 0; i <= n; i++){
    			r_safespaces.add(new ArrayList<>());
		}

		for (int i = 0; i <= m; i++){
			c_safespaces.add(new ArrayList<>());
		}
		for (int r = 1; r <= n; r++){
			String row = grid[r - 1];
			for (int c = 1; c <= m; c++){
				if (row.charAt(c - 1) == '.'){
					r_safespaces.get(r).add(c);
					c_safespaces.get(c).add(r);
				}
			}
		}
	
		for (int[] query : queries) {
    			int y1 = query[0];
    			int x1 = query[1];
    			int y2 = query[2];
    			int x2 = query[3];
			System.out.println(jump(y1, x1, y2, x2));
		}
	}
	static int jump(int y1, int x1, int y2, int x2) {
    		if (x1 == x2 && y1 == y2){
			return 0;
		}
		Queue<int[]> queue = new LinkedList<>();
		Set<String> visited = new HashSet<>();
		queue.add(new int[]{0, y1, 0});
		queue.add(new int[]{1, x1, 0});
		visited.add("r," + y1);
		visited.add("c," + x1);
		while (!queue.isEmpty()){
			int[] element = queue.poll();
			int tipe = element[0];
			int id = element[1];
			int distance = element[2];
			if (tipe == 0){
				if (id == y2 && r_safespaces.get(id).contains(x2)) {
					return distance+1;
				}
				for (int c : r_safespaces.get(id)) {
					if (!visited.contains("c," + c)) {
						visited.add("c," + c);
						queue.add(new int[]{1, c, distance + 1});
					}
				}
			}
			else{
				if (id == x2 && c_safespaces.get(id).contains(y2)) {
					return distance+1;
				}
				for (int r : c_safespaces.get(id)) {
					if (!visited.contains("r," + r)) {
						visited.add("r," + r);
						queue.add(new int[]{0, r, distance + 1});
					}
				}
			}
		
		}
		return -1;
    }
}
	




 

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