Hypyt

use std::io;
use std::collections::{
    HashMap,
    HashSet,
    VecDeque
};

fn main() {
    let mut input: String = String::new();
    io::stdin().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), HashSet<(usize, usize)>> = parse_graph(&input);
    
    for _ in 0..input[2] {
        let mut question: String = String::new();
        io::stdin().read_line(&mut question).unwrap();
        let question: Vec<usize> = question.trim().split(" ").map(|s| s.parse::<usize>().unwrap()).collect();

        println!("{}", calculate_path((question[0], question[1]), (question[2], question[3]), &graph));
    }
    
}

fn parse_graph(input: &Vec<usize>) -> HashMap<(usize, usize), HashSet<(usize, usize)>> {
    let mut graph: HashMap<(usize, usize), HashSet<(usize, usize)>> = HashMap::new();
    let mut nodes: HashSet<(usize, usize)> = HashSet::new();

    for r in 0..input[0] {
        let mut row: String = String::new();
        io::stdin().read_line(&mut row).unwrap();
        let row: Vec<_> = row.match_indices(".").collect();
        for node in row {
            let pos: (usize, usize) = (r + 1, node.0 + 1);
            graph.insert(pos, HashSet::new());
            nodes.insert(pos);
        }
    }
    get_neighbours(&mut graph, input, &nodes);

    return graph;
}

fn get_neighbours(graph: &mut HashMap<(usize, usize), HashSet<(usize, usize)>>, input: &Vec<usize>, nodes: &HashSet<(usize, usize)>) {
    for (pos, neighbours) in graph {
        for c in 0..input[1] {
            let neighbour: (usize, usize) = (pos.0, c + 1);
            if pos != &neighbour && nodes.contains(&neighbour) {
                neighbours.insert(neighbour);
            }
        }
        for r in 0..input[0] {
            let neighbour: (usize, usize) = (r + 1, pos.1);
            if pos != &neighbour && nodes.contains(&neighbour) {
                neighbours.insert(neighbour);
            }
        }
    }
}

fn calculate_path(start: (usize, usize), goal: (usize, usize), graph: &HashMap<(usize, usize), HashSet<(usize, usize)>>) -> i32 {
    let mut dist: HashMap<(usize, usize), i32> = HashMap::from([(start, 0)]);
    let mut visit_queue: VecDeque<(usize, usize)> = VecDeque::from([start]);

    while visit_queue.len() > 0 {
        let current: (usize, usize) =  visit_queue.pop_front().unwrap();
        if current == goal {
            return *dist.get(&current).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);
            }
        }
    }
        
    return -1;
}

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