Hypyt

use std::io::{
    self,
    BufReader,
    BufRead,
    Stdin
};
use std::collections::{
    HashMap, 
    HashSet,
    VecDeque
};
 
fn main() {
    let mut reader: BufReader<Stdin> = BufReader::new(io::stdin());
    
    let mut input: String = String::new();
    reader.read_line(&mut input).unwrap();
    let input: Vec<usize> = input.trim().split(" ").map(|s: &str| s.parse::<usize>().unwrap()).collect();

    let graph: HashMap<(usize, usize), Vec<(usize, usize)>> = parse_graph(&input, &mut reader);

    let mut queries_order: Vec<((usize, usize), (usize, usize))> = Vec::new();
    let mut queries: HashMap<(usize, usize), HashSet<(usize, usize)>> = HashMap::new();
    for _ in 0..input[2] {
        let mut query: String = String::new();
        reader.read_line(&mut query).unwrap();
        let query: Vec<usize> = query.trim().split(" ").map(|s: &str| s.parse::<usize>().unwrap()).collect();
 
        let start: (usize, usize) = (query[0], query[1]);
        let goal: (usize, usize) = (query[2], query[3]);
        
        queries_order.push((start, goal));
        queries.entry(start).and_modify(|s: &mut HashSet<(usize, usize)>| { s.insert(goal); }).or_insert(HashSet::from([goal]));
    }

    let distance_table: HashMap<(usize, usize), HashMap<(usize, usize), usize>> = get_distance_table(&graph, &queries);
    
    for query in queries_order {
        match distance_table.get(&query.0).unwrap().get(&query.1) {
            Some(dist) => { println!("{dist}"); }
            None => { println!("-1"); }
        }
    }
}
 
fn parse_graph(input: &Vec<usize>, reader: &mut BufReader<Stdin>) -> HashMap<(usize, usize), Vec<(usize, usize)>> {
    let mut graph: HashMap<(usize, usize), Vec<(usize, usize)>> = HashMap::new();
    let mut row_map: HashMap<usize, Vec<usize>> = HashMap::new();
    let mut col_map: HashMap<usize, Vec<usize>> = HashMap::new();
 
    for r in 0..input[0] {
        let mut row: String = String::new();
        reader.read_line(&mut row).unwrap();
        
        let mut c: usize = 1;
        for node in row.chars() {
            if node == '.' {
                graph.insert((r + 1, c), Vec::new());
                row_map.entry(r + 1).and_modify(|columns: &mut Vec<usize>| columns.push(c)).or_insert(Vec::from([c]));
                col_map.entry(c).and_modify(|columns: &mut Vec<usize>| columns.push(r + 1)).or_insert(Vec::from([r + 1]));
            }
            c += 1;
        }
    }
    get_neighbours(row_map, col_map, &mut graph);
 
    return graph;
}
 
fn get_neighbours(row_map: HashMap<usize, Vec<usize>>, col_map: HashMap<usize, Vec<usize>>, graph: &mut HashMap<(usize, usize), Vec<(usize, usize)>>) {
    for (pos, neighbours) in graph {
        for c in row_map.get(&pos.0).unwrap() {
            let neighbour: (usize, usize) = (pos.0, *c);
            if &neighbour != pos {
                neighbours.push(neighbour);
            }
        }
        for r in col_map.get(&pos.1).unwrap() {
            let neighbour: (usize, usize) = (*r, pos.1);
            if &neighbour != pos {
                neighbours.push(neighbour);
            }
        }
    }
}
 
fn get_distance_table(graph: &HashMap<(usize, usize), Vec<(usize, usize)>>, queries: &HashMap<(usize, usize), HashSet<(usize, usize)>>) -> HashMap<(usize, usize), HashMap<(usize, usize), usize>> {
    let mut table: HashMap<(usize, usize), HashMap<(usize, usize), usize>> = HashMap::new();
 
    for (start, goals) in queries {
        table.insert(*start, HashMap::new());
        bfs(*start, graph, &mut table, goals);
    }
 
    return table;
}
 
fn bfs(root: (usize, usize), graph: &HashMap<(usize, usize), Vec<(usize, usize)>>, table: &mut HashMap<(usize, usize), HashMap<(usize, usize), usize>>, goals: &HashSet<(usize, usize)>) {
    let dist: &mut HashMap<(usize, usize), usize> = table.get_mut(&root).unwrap();
    dist.insert(root, 0);
    let mut visit_queue: VecDeque<(usize, usize)> = VecDeque::from([root]);
    let mut visited: HashSet<(usize, usize)> = HashSet::new();
 
    while visit_queue.len() > 0 {
        let current: (usize, usize) = visit_queue.pop_front().unwrap();
 
        for neighbour in graph.get(&current).unwrap() {
            if !dist.contains_key(neighbour) {
                dist.insert(*neighbour, *dist.get(&current).unwrap() + 1);
                visit_queue.push_back(*neighbour);
                if goals.contains(neighbour) { visited.insert(*neighbour); };
            }
        }

        if visited.eq(goals) {
            break;
        }
    }
}

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

Test 9

Group: 3, 4, 5

Verdict: TIME LIMIT EXCEEDED

Test 10

Group: 3, 4, 5

Verdict: ACCEPTED

Test 11

Group: 3, 4, 5

Verdict: ACCEPTED

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

Test 20

Group: 5

Verdict: ACCEPTED

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

Test 25

Group: 5

Verdict: ACCEPTED

Test 26

Group: 5

Verdict: RUNTIME ERROR

Test 27

Group: 5

Verdict: ACCEPTED