Hypyt

import java.util.Arrays;
import java.util.BitSet;
import java.util.Scanner;

public class E {
    private final BitSet[] rows;
    private final BitSet[] columns;

    private final int width;
    private final int height;

    private final short[] distanceToCol;
    private final short[] distanceToRow;

    private E(BitSet[] rows, BitSet[] columns) {
        this.rows = rows;
        this.columns = columns;
        height = rows.length;
        width = columns.length;
        distanceToCol = new short[width * height * width];
        distanceToRow = new short[width * height * height];

        Arrays.fill(distanceToRow, (short) -1);
        Arrays.fill(distanceToCol, (short) -1);
    }

    public static void main(String[] args) {
        var sc = new Scanner(System.in);
        var height = sc.nextInt();
        var width = sc.nextInt();
        var nQueries = sc.nextInt();
        sc.nextLine();

        var rows = new BitSet[height];
        for (var i = 0; i < height; i++) {
            var chars = sc.nextLine().toCharArray();
            var bitset = new BitSet();
            for (var j = 0; j < chars.length; j++) {
                if (chars[j] != '*') {
                    bitset.set(j);
                }
            }
            rows[i] = bitset;
        }

        var columns = new BitSet[width];
        for (var i = 0; i < columns.length; i++) {
            var bitset = new BitSet();
            for (var j = 0; j < rows.length; j++) {
                bitset.set(j, rows[j].get(i));
            }
            columns[i] = bitset;
        }

        var state = new E(rows, columns);
        for (var row = 0; row < height; row++) {
            for (var col = 0; col < width; col++) {
//                System.out.println(row + " " + col);
                state.doPathfind(row, col);
            }
        }

        for (var i = 0; i < nQueries; i++) {
            var row1 = sc.nextInt() - 1;
            var col1 = sc.nextInt() - 1;
            var row2 = sc.nextInt() - 1;
            var col2 = sc.nextInt() - 1;
            sc.nextLine();

            var colDistance = state.distanceToCol[col2 + row1 * width + col1 * width * height];
            var rowDistance = state.distanceToRow[row2 + row1 * height + col1 * height * height];
//            System.out.printf("%s, %s -> ", colDistance, rowDistance);
            if (colDistance == 0 && rowDistance == 0) {
                System.out.println(0);
            } else if (colDistance == -1 && rowDistance == -1) {
                System.out.println(-1);
            } else {
                System.out.println(Math.min(rowDistance, colDistance) + 1);
            }
        }
    }

    private void doPathfind(int row, int col) {
        // Visited rows and columns, don't touch these
        var visitedRows = new BitSet();
        var visitedCols = new BitSet();

        // Current distance from start cell
        short distance = 0;

        // The rows and columns that we are currently checking
        var activeRows = new BitSet();
        activeRows.set(row);
        var activeCols = new BitSet();
        activeCols.set(col);

        // Here we store rows and columns that we can reach from the active ones
        var nextRows = new BitSet();
        var nextCols = new BitSet();

        while (!activeRows.isEmpty() || !activeCols.isEmpty()) {
            //System.out.printf("d: %s, ar: %s, ac: %s%n", distance, activeRows, activeCols);
            for (var activeRow = activeRows.nextSetBit(0); activeRow != -1; activeRow = activeRows.nextSetBit(activeRow + 1)) {
                distanceToRow[activeRow + row * height + col * height * height] = distance;
                nextCols.or(rows[activeRow]);
            }
            for (var activeCol = activeCols.nextSetBit(0); activeCol != -1; activeCol = activeCols.nextSetBit(activeCol + 1)) {
                distanceToCol[activeCol + row * width + col * width * height] = distance;
                nextRows.or(columns[activeCol]);
            }

            {
                // Mark active as visited so that we don't go back
                visitedRows.or(activeRows);

                // Swap active and next to avoid allocations
                var temp = activeRows;
                activeRows = nextRows;
                nextRows = temp;

                // Remove visited from active
                activeRows.andNot(visitedRows);
                // Empty next
                nextRows.clear();
            }
            {
                // Same as above
                visitedCols.or(activeCols);

                var temp = activeCols;
                activeCols = nextCols;
                nextCols = temp;

                activeCols.andNot(visitedCols);
                nextCols.clear();
            }
            distance++;
        }

    }
}

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