Hypyt

warning: unused variable: `qn`
   --> input/code.rs:146:13
    |
146 |         let qn = (*xn, y, x2, y2);
    |             ^^ help: if this is intentional, prefix it with an underscore: `_qn`
    |
    = note: `#[warn(unused_variables)]` on by default

warning: unused variable: `qn`
   --> input/code.rs:177:13
    |
177 |         let qn = (x, *yn, x2, y2);
    |             ^^ help: if this is intentional, prefix it with an underscore: `_qn`

warning: 2 warnings emitted

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

fn q_itr(q: usize) -> impl Iterator<Item = (usize, usize, usize, usize)> {
    (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 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 queries: Vec<(usize, usize, usize, usize)> = q_itr(q).collect();
    // let q_in_order = queries.clone();
    // queries.sort_unstable();
    let mut results = HashMap::with_capacity(q);
    for qry in &queries {
        let iqry = (qry.2, qry.3, qry.0, qry.1);
        let a;
        if let Some(r) = results.get(qry) {
            a = *r;
        } else if let Some(r) = results.get(&iqry) {
            a = *r;
        } else {
            a = p_recur(
                qry.0,
                qry.1,
                qry.2,
                qry.3,
                &sc,
                &sr,
                alr_vis.clone(),
                &mut results,
            );
            results.insert(*qry, a);
        }
        println!("{}", a);
    }
}

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

fn p_recur(
    x: usize,
    y: usize,
    x2: usize,
    y2: usize,
    sc: &[Vec<usize>],
    sr: &[Vec<usize>],
    mut alr_vis: Vec<Vec<bool>>,
    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 0;
    }
    let q = (x, y, x2, y2);
    let qi = (x2, y2, x, y);
    if let Some(d) = s_paths.get(&q) {
        return *d;
    }
    if let Some(d) = s_paths.get(&qi) {
        return *d;
    }
    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_paths);
        // println!(
        //     "(y, x) = ({}, {}), (y2, x2) = ({}, {}), r = {}",
        //     y + 1,
        //     xn + 1,
        //     y2 + 1,
        //     x2 + 1,
        //     r
        // );
        // print!("Already visited: ");
        // for i in 0..alr_vis.len() {
        //     for j in 0..alr_vis[i].len() {
        //         if alr_vis[i][j] {
        //             print!("({}, {}) ", j + 1, i + 1);
        //         }
        //     }
        // }
        // println!();
        let qn = (*xn, y, x2, y2);
        // s_paths.insert(qn, r);
        if r != -1 && (m == -1 || r < m) {
            m = r;
            // if m <= 1 {
            //     return m + 1;
            // }
        }
    }
    for yn in &sc[x] {
        if *yn == y {
            continue;
        }
        let r = p_recur(x, *yn, x2, y2, sc, sr, alr_vis.clone(), s_paths);
        // println!(
        //     "(y, x) = ({}, {}), (y2, x2) = ({}, {}), r = {}",
        //     yn + 1,
        //     x + 1,
        //     y2 + 1,
        //     x2 + 1,
        //     r
        // );
        // print!("Already visited: ");
        // for i in 0..alr_vis.len() {
        //     for j in 0..alr_vis[i].len() {
        //         if alr_vis[i][j] {
        //             print!("({}, {}) ", j + 1, i + 1);
        //         }
        //     }
        // }
        // println!();
        let qn = (x, *yn, x2, y2);
        // s_paths.insert(qn, r);
        if r != -1 && (m == -1 || r < m) {
            m = r;
            // if m <= 1 {
            //     return m + 1;
            // }
        }
    }
    if m == -1 {
        return -1;
    } else {
        return m + 1;
    }
}

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