Hypyt

use std::io::stdin;

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 mut queries = Vec::with_capacity(q);
    for _ in 0..q {
        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;
        queries.push((x1, y1, x2, y2));
    }
    let mut alr_vis = Vec::with_capacity(m);
    for _ in 0..m {
        let mut v = Vec::with_capacity(n);
        for _ in 0..n {
            v.push(false);
        }
        alr_vis.push(v);
    }
    for qry in queries {
        println!(
            "{}",
            p_recur(qry.0, qry.1, qry.2, qry.3, &sc, &sr, alr_vis.clone(), 0)
        );
    }
}

/*
 * 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
 *
 * 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
 * */

fn p_recur(
    x: usize,
    y: usize,
    x2: usize,
    y2: usize,
    sc: &[Vec<usize>],
    sr: &[Vec<usize>],
    mut alr_vis: Vec<Vec<bool>>,
    s: isize,
) -> isize {
    if alr_vis[x][y] {
        return -1;
    }
    alr_vis[x][y] = true;
    if x == x2 && y == y2 {
        return s;
    }
    let mut m = -1;
    for xn in &sr[y] {
        if *xn == x {
            continue;
        }
        let r = p_recur(*xn, y, x2, y2, sc, sr, alr_vis.clone(), s + 1);
        if r != -1 && (m == -1 || r < m) {
            m = r;
        }
    }
    for yn in &sc[x] {
        if *yn == y {
            continue;
        }
        let r = p_recur(x, *yn, x2, y2, sc, sr, alr_vis.clone(), s + 1);
        if r != -1 && (m == -1 || r < m) {
            m = r;
        }
    }
    return m;
}

Test 1 (public)

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

Test 2

Group: 1, 2, 3, 4, 5

Verdict: TIME LIMIT EXCEEDED

Test 3

Group: 1, 2, 3, 4, 5

Verdict: TIME LIMIT EXCEEDED

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