Hypyt

use std::{collections::HashMap, 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 q_in_order = queries.clone();
    // queries.sort_unstable();
    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);
    }
    let mut results = HashMap::with_capacity(q);
    for qry in &queries {
        if !results.contains_key(qry) {
            let r = p_recur(
                qry.0,
                qry.1,
                qry.2,
                qry.3,
                &sc,
                &sr,
                alr_vis.clone(),
                0,
                &mut results,
            );
            results.insert(*qry, r);
        }
        println!("{}", results[qry]);
    }
}

/*
 * 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,
    s_paths: &mut HashMap<(usize, usize, usize, usize), isize>,
) -> isize {
    if alr_vis[x][y] {
        return -1;
    }
    alr_vis[x][y] = true;
    if x == x2 && y == y2 {
        return s;
    }
    let q = (x, y, x2, y2);
    if s_paths.contains_key(&q) {
        return s + s_paths[&q];
    }
    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, s_paths);
        if r != -1 && (m == -1 || r < m) {
            m = r;
            if m == s + 1 {
                return m;
            }
        }
    }
    for yn in &sc[x] {
        if *yn == y {
            continue;
        }
        let r = p_recur(x, *yn, x2, y2, sc, sr, alr_vis.clone(), s + 1, s_paths);
        if r != -1 && (m == -1 || r < m) {
            m = r;
        }
        if m == s + 1 {
            return m;
        }
    }
    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: ACCEPTED

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