Hypyt

use std::io::{
    BufReader,
    BufRead,
    stdin,
    Stdin
};
use std::collections::{
    HashMap, 
    HashSet,
    VecDeque
};

#[derive(Clone, Copy, PartialEq, Eq, Hash)]
enum Node {
    Cell((usize, usize)),
    Row(usize),
    Column(usize)
}

fn main() {
    let mut reader: BufReader<Stdin> = BufReader::new(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 mut graph: HashMap<Node, Vec<Node>> = HashMap::new();
    parse_graph(&input, &mut reader, &mut graph);

    let mut queries: HashMap<Node, HashSet<Node>> = HashMap::new();
    let mut queries_order: Vec<(Node, Node)> = Vec::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: Node = Node::Cell((query[0], query[1]));
        let goal: Node = Node::Cell((query[2], query[3]));
        queries.entry(start).or_insert_with(HashSet::new).insert(goal);
        queries_order.push((start, goal));
    }

    let mut distance_table: HashMap<Node, HashMap<Node, usize>> = HashMap::new();
    get_distance_table(&mut distance_table, &graph, &queries);

    for (start, goal) in queries_order {
        if let Some(dist) = distance_table.get(&start).unwrap().get(&goal) {
            println!("{}", dist/2);
        } else {
            println!("-1")
        }
    }
}

fn parse_graph(input: &Vec<usize>, reader: &mut BufReader<Stdin>, graph: &mut HashMap<Node, Vec<Node>>) {
    for r in 0..input[0] {
        let mut row: String = String::new();
        reader.read_line(&mut row).unwrap();
        
        for (c, cell) in row.chars().enumerate() {
            if cell == '.' {
                graph.insert(Node::Cell((r + 1, c + 1)), Vec::from([Node::Row(r + 1), Node::Column(c + 1)]));
                graph.entry(Node::Row(r + 1)).or_insert_with(Vec::new).push(Node::Cell((r + 1, c + 1)));
                graph.entry(Node::Column(c + 1)).or_insert_with(Vec::new).push(Node::Cell((r + 1, c + 1)));
            }
        }
    }
}

fn get_distance_table(table: &mut HashMap<Node, HashMap<Node, usize>>, graph: &HashMap<Node, Vec<Node>>, queries: &HashMap<Node, HashSet<Node>>) {
    for (&root, goals) in queries {
        table.insert(root, HashMap::new());
        bfs(root, goals, table.get_mut(&root).unwrap(), graph);
    }
}

fn bfs(start: Node, goals: &HashSet<Node>, dist: &mut HashMap<Node, usize>, graph: &HashMap<Node, Vec<Node>>) {
    dist.insert(start, 0);
    let mut queue: VecDeque<Node> = VecDeque::from([start]);
    let goals_count: usize = goals.len();
    let mut goals_visited: usize = 0;

    while let Some(current) = queue.pop_front() {
        for neighbour in graph.get(&current).unwrap() {
            if !dist.contains_key(neighbour) {
                dist.insert(*neighbour, dist.get(&current).unwrap() + 1);
                queue.push_back(*neighbour);
                if goals.contains(neighbour) {
                    goals_visited += 1;
                }
            }
        }
        if goals_visited == goals_count {
            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: 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: ACCEPTED

Test 25

Group: 5

Verdict: ACCEPTED

Test 26

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 27

Group: 5

Verdict: ACCEPTED