Hypyt

use std::{
    collections::{HashMap, HashSet},
    io::stdin,
    isize, usize,
};

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)
    })
}

#[derive(PartialEq, Eq, Hash, Clone, Copy)]
struct LQuery {
    sl: usize,
    gl: usize,
}

impl LQuery {
    pub fn new(l1: usize, l2: usize) -> LQuery {
        if l1 > l2 {
            LQuery { gl: l1, sl: l2 }
        } else {
            LQuery { gl: l2, sl: l1 }
        }
    }
}

#[derive(Clone, Copy)]
struct PSet {
    d: [u64; 4],
}

impl PSet {
    pub fn new() -> PSet {
        PSet { d: [0; 4] }
    }
    pub fn push(&mut self, k: usize) {
        self.d[k / 64] |= PSet::bp(k);
    }
    #[inline]
    fn bp(k: usize) -> u64 {
        1 << (k % 64)
    }
    pub fn contains(&self, k: usize) -> bool {
        let t = self.d[k / 64] & PSet::bp(k);
        t > 0
    }
    pub fn union(&mut self, other: &PSet) {
        self.d[0] |= other.d[0];
        self.d[1] |= other.d[1];
        self.d[2] |= other.d[2];
        self.d[3] |= other.d[3];
    }
    pub fn is_empty(&self) -> bool {
        self.d[0] | self.d[1] | self.d[2] | self.d[3] == 0
    }
}

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 sc: Vec<HashSet<usize>> = Vec::new();
    let mut sr: Vec<HashSet<usize>> = Vec::new();
    for _ in 0..n {
        sr.push(HashSet::new());
    }
    for _ in 0..m {
        sc.push(HashSet::new());
    }
    let mut r_ts: HashMap<LQuery, PSet> = HashMap::new();
    let mut c_ts: HashMap<LQuery, PSet> = HashMap::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].insert(j);
                sc[j].insert(i);
            }
        }
    }
    for i in 0..n {
        for j in 0..n {
            let lq = LQuery::new(i, j);
            if r_ts.contains_key(&lq) {
                continue;
            }
            r_ts.insert(lq, PSet::new());
            for c in 0..m {
                if sc[c].contains(&i) && sc[c].contains(&j) {
                    unsafe {
                        r_ts.get_mut(&lq).unwrap_unchecked().push(c);
                    }
                }
            }
        }
    }
    for i in 0..m {
        for j in 0..m {
            let lq = LQuery::new(i, j);
            if c_ts.contains_key(&lq) {
                continue;
            }
            c_ts.insert(lq, PSet::new());
            for r in 0..n {
                if sr[r].contains(&i) && sr[r].contains(&j) {
                    unsafe {
                        c_ts.get_mut(&lq).unwrap_unchecked().push(r);
                    }
                }
            }
        }
    }
    let queries: Vec<Query> = q_itr(q).collect();
    test_group2_5(n, m, &queries, &r_ts, &c_ts);
}

struct LineOptimalSet {
    vp: PSet,
    d: isize,
}

fn test_group2_5(
    n: usize,
    m: usize,
    queries: &[Query],
    r_ts: &HashMap<LQuery, PSet>,
    c_ts: &HashMap<LQuery, PSet>,
) {
    let mut row_os = HashMap::with_capacity(n * n);
    let mut column_os = HashMap::with_capacity(m * m);
    let mut r_ds = HashMap::with_capacity(n * n);
    let mut c_ds = HashMap::with_capacity(m * m);
    compute_all_ds(n, &r_ts, &mut r_ds);
    compute_all_ds(m, &c_ts, &mut c_ds);
    for i in 0..n {
        for j in 0..n {
            compute_line_optimal_set(n, i, j, &mut row_os, r_ts, &mut r_ds);
        }
    }
    for i in 0..m {
        for j in 0..m {
            compute_line_optimal_set(m, i, j, &mut column_os, c_ts, &mut c_ds);
        }
    }
    for q in queries {
        let d = tg2_5_qry(*q, &row_os, &column_os);
        println!("{}", d);
    }
}

fn compute_all_ds(n: usize, l_ts: &HashMap<LQuery, PSet>, ds: &mut HashMap<LQuery, isize>) {
    for i in 0..n {
        for j in 0..n {
            let lij = LQuery::new(i, j);
            if i == j {
                ds.insert(lij, 0);
            } else if !l_ts[&lij].is_empty() {
                ds.insert(lij, 1);
            } else {
                ds.insert(lij, -1);
            }
        }
    }
    for k in 0..n {
        for i in 0..n {
            for j in 0..n {
                let lij = LQuery::new(i, j);
                let ik = ds[&LQuery::new(i, k)];
                let kj = ds[&LQuery::new(k, j)];
                if ik == -1 || kj == -1 {
                    continue;
                }
                let d = ik + kj;
                if d < ds[&lij] || ds[&lij] == -1 {
                    ds.insert(lij, d);
                }
            }
        }
    }
}

fn compute_line_optimal_set(
    n: usize,
    l1: usize,
    l2: usize,
    line_os: &mut HashMap<(usize, usize), LineOptimalSet>,
    l_ts: &HashMap<LQuery, PSet>,
    ds: &mut HashMap<LQuery, isize>,
) {
    let lp12 = (l1, l2);
    if line_os.contains_key(&lp12) {
        return;
    }
    let vp = &l_ts[&LQuery::new(l1, l2)];
    if !vp.is_empty() {
        line_os.insert(
            lp12,
            LineOptimalSet {
                d: 1,
                vp: vp.clone(),
            },
        );
        return;
    } else {
        let mut lis = Vec::new();
        let mut sd = isize::MAX - 1;
        for li in 0..n {
            if li == l1 || li == l2 {
                continue;
            }
            let l1_i = LQuery::new(l1, li);
            if l_ts[&l1_i].is_empty() {
                continue;
            }
            let d = ds[&LQuery::new(li, l2)];
            if d == -1 {
                continue;
            }
            if d <= sd {
                if d < sd {
                    lis.clear();
                }
                lis.push(li);
                sd = d;
            }
        }
        if sd == isize::MAX - 1 {
            line_os.insert(
                lp12,
                LineOptimalSet {
                    d: -1,
                    vp: PSet::new(),
                },
            );
            return;
        }
        let mut vp = PSet::new();
        for li in lis {
            let l1_i = LQuery::new(l1, li);
            let vp1i = &l_ts[&l1_i];
            vp.union(vp1i);
        }
        line_os.insert(lp12, LineOptimalSet { d: 1 + 2 * sd, vp });
    }
}

fn tg2_5_qry(
    q: Query,
    row_os: &HashMap<(usize, usize), LineOptimalSet>,
    column_os: &HashMap<(usize, usize), LineOptimalSet>,
) -> isize {
    if q.0 == q.2 && q.1 == q.3 {
        return 0;
    } else if q.0 == q.2 || q.1 == q.3 {
        return 1;
    } else {
        let rpq = (q.1, q.3);
        let cpq = (q.0, q.2);
        let rp = &row_os[&rpq];
        let cp = &column_os[&cpq];
        let mut rd = rp.d;
        let mut cd = cp.d;
        if rd == -1 && cd == -1 {
            return -1;
        }
        if rd != -1 && !rp.vp.contains(q.0) {
            rd += 1;
        }
        if cd != -1 && !cp.vp.contains(q.1) {
            cd += 1;
        }
        if rd == -1 || (cd != -1 && cd < rd) {
            rd = cd;
        }
        return rd + 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 something 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 to 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
 * */
/*
 * 1. Every edge in the path from r1 to r2 will either have weight 1 or 2. The first edge will always
 * have weight 1.
 * 2. An edge has weight 1 if its OSET intersects with the intersection of the OSETs of all the previous edges with
 *    weight 1 plus the last edge with weight 2 before those edges. Otherwise, the edge has weight 2. An edge with
 *    weight 2 always breaks of the weight 1 chain (in the sense that for every edge after an edge
 *    with weight 2, the edges before that weight 2 edge don't matter for the weight of the new
 *    edge), and potentially starts a new one.
 * 3. The first potential weight 1 chain starts with the very first edge of the path, which always
 *    has weight 1. Every future weight 1 chain starts with a weight 2 edge.
 * 4. For the first weight 1 chain, it can be replaced simply with a weight 1 edge connecting the
 *    first node in the path with the last node of the chain. If the chain has more than 1
 *    node, this always yields a strictly shorter path. For all subsequent weight 1 chains, all
 *    the weight 1 edges can be removed entirely, and the weight 2 edge preceding the weight 1
 *    chain be replaced with a weight 2 edge leading directly to the last node in the weight 1
 *    chain. This is always strictly faster, even if there is only one node in the weight 1
 *    chain.
 * 5. For a path which is among those with the least distance between r1 and r2, there can be no
 *    edges with weight 1 in any place except the very first edge of the path, which always must
 *    have weight 1.
 * 6. The optimal set of every path is simply the optimal set of the transition between r1 and the
 *    first intermediate node. The distance of the path is simply 2(n - 1) + 1 = 2n - 3, where n
 *    is the number of nodes.
 * 7. The shortest path is simply determined by the path with the least amount of nodes.
 * 8. Any algorithm which finds the path with the least number of nodes will never output any paths
 *    which contain any weight 1 edges beyond the first edge in the path, as in those cases the
 *    number of nodes could be reduced as outlined in (4).
 * 9. The problem is thus reduced to a standard problem of finding the path with the least nodes,
 *    with one important catch: it is required to also find all other paths with the same distance
 *    as the path with the shortest distance, in order to fully determine the optimal set of the
 *    shortest path.
 * 10. Only those paths where the 2nd node (i.e, the first intermediate node) differs are required.
 *
 * */

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

Test 10

Group: 3, 4, 5

Verdict: ACCEPTED

Test 11

Group: 3, 4, 5

Verdict: ACCEPTED

Test 12

Group: 4, 5

Verdict: ACCEPTED

Test 13

Group: 4, 5

Verdict: ACCEPTED

Test 14

Group: 4, 5

Verdict: ACCEPTED

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