Hypyt

use std::{collections::HashMap, io::stdin};

type Query = (usize, usize, usize, usize);

fn q_itr(q: usize) -> impl Iterator<Item = Query> {
    (0..q).map(|_| {
        let mut ln = String::new();
        stdin().read_line(&mut ln).unwrap();
        let mut litr = ln.split_ascii_whitespace();
        let y1 = litr.next().unwrap().parse::<usize>().unwrap() - 1;
        let x1 = litr.next().unwrap().parse::<usize>().unwrap() - 1;
        let y2 = litr.next().unwrap().parse::<usize>().unwrap() - 1;
        let x2 = litr.next().unwrap().trim_end().parse::<usize>().unwrap() - 1;
        (x1, y1, x2, y2)
    })
}

fn main() {
    let mut l = String::new();
    stdin().read_line(&mut l).unwrap();
    let mut itr = l.split_ascii_whitespace();
    let n: usize = itr.next().unwrap().parse().unwrap();
    let m: usize = itr.next().unwrap().parse().unwrap();
    let q: usize = itr.next().unwrap().trim_end().parse().unwrap();
    let mut sr: Vec<Vec<usize>> = Vec::with_capacity(n);
    let mut sc: Vec<Vec<usize>> = Vec::with_capacity(m);
    for _ in 0..n {
        sr.push(Vec::new());
    }
    for _ in 0..m {
        sc.push(Vec::new());
    }
    for i in 0..n {
        let mut ln = String::new();
        stdin().read_line(&mut ln).unwrap();
        for (j, c) in ln.chars().enumerate() {
            if c == '.' {
                sr[i].push(j);
                sc[j].push(i);
            }
        }
    }

    let queries: Vec<Query> = q_itr(q).collect();
    test_group1(&sc, &sr, &queries);
}

fn test_group1(sc: &[Vec<usize>], sr: &[Vec<usize>], queries: &[Query]) {
    for q in queries {
        let d = tg1_qry(q, sc, sr);
        println!("{}", d);
    }
}

fn tg1_qry(q: &Query, sc: &[Vec<usize>], sr: &[Vec<usize>]) -> isize {
    let mut ae = HashMap::new();
    let mut v1 = Vec::new();
    let mut v2 = Vec::new();
    v1.push((q.0, q.1));
    let mut ce = &mut v1;
    let mut ne = &mut v2;
    let mut d = 0;
    while ce.len() > 0 {
        for e in ce.iter() {
            if e.0 == q.2 && e.1 == q.3 {
                return d;
            }
            for ny in &sc[e.0] {
                let el = (e.0, *ny);
                if !ae.contains_key(&el) {
                    ae.insert(el, true);
                    ne.push(el);
                }
            }
            for nx in &sr[e.1] {
                let el = (*nx, e.1);
                if !ae.contains_key(&el) {
                    ae.insert(el, true);
                    ne.push(el);
                }
            }
        }
        ce.clear();
        let tmp = ce;
        ce = ne;
        ne = tmp;
        d += 1;
    }
    return -1;
}

/*
 * Problem:
 * State: S(x,y)
 * Goal: S(x, y) = G(x2, y2)
 * Available options at S(x,y) = N(x,y)
 * Task: Find the path P(S1, S2, S3, ..., SN) with the minimum N
 *
 * Additional properties:
 * Property One: If S1 in S2N then S2 in S1N -> undirected graph, with Sk as the nodes
 * Property Two: SkN divided into two sets: one where x = Sk.x and the other where y = Sk.y
 * Property Three: Up to 2 * 10^5 queries made simultaneoously, instead of only one. I.e, need to
 * make heavy use of previous results.
 *
 * Possible solutions:
 * 1. Trivial algorithm for finding minimum path between two nodes in a given graph
 * 2. Well-known and more optimal algorithm for finding minimum path between two nodes in a given
 *    graph
 * 3. Hand-crafted algorithm also making use of the second property
 *
 *
 * BFS: O((nm + nm(n - 1 + m - 1))) = O(nmq(n + m - 1))
 *
 * Observations for the hardest setting of the hardest test group:
 * 1. q = 2*10^5. Therefore the time complexity for processing each individual query needs to be roughly O(1).
 * 2. A good way to accomplish this seems to be going through the grid first and generating some
 *    data which would allow some akin to a simple lookup from a table in order to process a given
 *    query.
 * 3. Total node count is mn = 250^2 = 62500. Thus the amount of node pairs is
 *    (250^2)^2 ~= 3.9 * 10^9. Processing through all of them would require too many cycles,
 *    and it is too many items to store in memory anyway, requiring a hashmap of over 4GB of memory.
 * 4. This data would have to exploit some redundancies in data storage derived from the
 *    regularities in the computation of the shortest path.
 * 5. Properties for a given query (xo, yo, xt, yt), where d represents the shortest path for that
 *    query:
 * 5.1 If xo = xt and yo = yt then d = 0.
 * 5.2 Travelling to a point (x2, y2) from a point (x1, y1) always takes only one step when one of x1 =
 *   x2 or y2 = y1 is true. This is because in that case, both points are safe rooms of a given row
 *   or column, and as per the definition of the problem, it always takes exactly one step to
 *   travel from a given safe room to a different safe room in the same row or column.
 * 5.3 If only one of xo = xt or yo = yt, then d = 1. (From 5.2)
 * 5.4 In the third case of xo != xt and yo != yt:
 *     5.4.1 For whatever form the shortest path takes, it must include as its 2nd last step transferring
 *     into the row or column of yt or xt respectively. This step must occur at some point because the
 *     path ends when x = xt and y = yt. This step must be the second last step because of 5.2.
 *     5.4.2 Two cases for the shortest path: A) a path that first leads into the same row as the
 *     target room B) a path that first leads into the same column as the target room.
 *     5.4.3 The shortest path is min(A, B) + 1. (From 5.4.2)
 *     5.4.4 The problem can be reformulated as travelling from a given row or column to a given target row or column respectively. (From 5.4.3)
 *     5.4.5 The cases of travelling from row to row and from column to column are symmetric,
 *     therefore WLOG let's consider the case of row to row (r1 = starting row, r2 = target row):
 *         1) d depends on the starting column within the row.
 *         2) There is a set of columns within a row for which d is lowest
 *         3) For any columns outside of that set, the shortest path is d + 1. (From 5.2)
 *         4) The shortest paths can thus be reduced without loss of information into just the
 *            d for the set of columns within the row for which the path is the shortest. Let's
 *            call this set the row's optimal set. (From 1 - 3)
 *         5) If the row has any columns along which the target row also has a safe room, then the
 *            row's optimal set is those columns and its d = 1.
 *         6) Otherwise, the shortest path from r1 to r2 must include travelling to one or multiple
 *            intermediate rows, where an intermediate row is defined to be a row to which it is
 *            possible to directly travel from r1. Therefore in this case, the shortest path from
 *            r1 to r2 will be determined recursively by comparing the shortest
 *            paths of the various intermediate row options (need to also take into account the
 *            fact that different intermediate rows are accessible from different columns).
 *                6.1) For a given intermediate row, the shortest path through that intermediate
 *                  row is calculated as the sum of the shortest path to that row from r1 and from
 *                  there to r2. This is effectively an O(1) operation, as both of these term are
 *                  among the 250^2 optimal sets for row pairs that need to be calculated anyway.
 *                6.2) Comparing the value calculated as in 6.1 accross all 248 possible intermediate
 *                  rows and selecting the lowest one is thus O(250). Because this needs to be done
 *                  for all 250^2 row pairs, in total the whole computation of optimal sets for all
 *                  row pairs takes 250^3 ~= 1.6 * 10^7 cycles. This should be acceptable.
 *                6.3) In terms of the column dimension of the task, the optimal set of r1 to ri
 *                  row pair is by definition the same as the set of columns from which within r1
 *                  it is possible to directly travel in one step to ri. The optimal set of the
 *                  whole operation of travelling from r1 to r2 will be a subset of the optimal set
 *                  from r1 to ri, as if the starting column was outside of the optimal set of r1 to
 *                  ri, then that would only add an extra step to the path as it would be
 *                  required to travel to a column within the optimal set of r1 to ri
 *                  before doing anything else in order to be able to even travel to ri.
 *                  If the optimal sets of r1 to ri and ri to r2 have an intersection, then this
 *                  intersection will be the optimal set of r1 to r2, and the d of r1 to
 *                  r2 will be the d of r1 to ri + the d of ri to r2. If there is no
 *                  intersection, then the optimal set of r1 to r2 will simply be the same
 *                  as the optimal set of r1 to ri and the d will be that of the previous
 *                  case incremented by one.
 *         7) Since m, n = 250 and 250^2 = 62500, it is also entirely feasible to compute and store the
 *            optimal sets for every row pair in an array.
 *     5.4.6 Once the optimal sets for every row pair and every column pair have been computed and
 *     stored (before processing the queries), A and B can be computed simply by looking up the d
 *     stored for optimal set of the given row or column pair, and then incrementing that by 1 if
 *     the starting position within the row or column falls outside the optimal set.
 *     5.4.7 Thus every query can be processed in O(1) in this way.
 *     5.4.8 Worst case total cycles of the whole task implemented this way should be 2 * 250^3 + 4 * 10^5 ~= 3.2 * 10^7.
 *     Worst case total memory should be 2 * 250^2 * (sizeof([usize; 249]) + sizeof(usize)) = 250^3 * 16
 *     bytes = 2.5 * 10^8 bytes = 250 MB
 * */

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