Hypyt

use std::cmp::Ordering;
use std::io;
use std::collections::{BinaryHeap, HashMap, HashSet};

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
struct Node {
    position: (usize, usize),
    cost: usize,
    heuristic: usize,
    value: usize,
    parent: Option<(usize, usize)>
}
impl Ord for Node {
    fn cmp(&self, other: &Self) -> Ordering {
        other.value.cmp(&self.value).then_with(|| other.heuristic.cmp(&self.heuristic)).then_with(|| self.position.0.cmp(&other.position.0)).then_with(|| self.position.1.cmp(&other.position.1))
    }
}
impl PartialOrd for Node {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}
impl Node {
    fn update(&mut self, current: &Self, goal: (usize, usize)) {
        self.cost = current.cost + 1;
        self.heuristic = calculate_heuristic(self.position, goal);
        self.value = self.cost + self.heuristic;
        self.parent = Some(current.position);
    }
}

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 nodes: HashMap<(usize, usize), Node> = parse_nodes(&input);
    let neighbours: HashMap<(usize, usize), Vec<(usize, usize)>> = get_all_neighbours(&nodes, &input);

    for _ in 0..input[2] {
        let mut points: String = String::new();
        io::stdin().read_line(&mut points).unwrap();
        let points: Vec<usize> = points.trim().split(" ").map(|s| s.parse::<usize>().unwrap()).collect();

        println!("{}", calculate_path((points[0], points[1]), (points[2], points[3]), nodes.clone(), &neighbours))
    }
}

fn parse_nodes(input: &Vec<usize>) -> HashMap<(usize, usize), Node> {
    let mut nodes: HashMap<(usize, usize), Node> = HashMap::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 n in row {
            let pos: (usize, usize) = (r + 1, n.0 + 1);
            let node: Node = Node { position: pos, cost: 0, heuristic: 0, value: 0, parent: None };
            nodes.insert(pos, node);
        }
    }

    return nodes;
}

fn get_all_neighbours(nodes: &HashMap<(usize, usize), Node>, input: &Vec<usize>) -> HashMap<(usize, usize), Vec<(usize, usize)>> {
    let mut neighbours: HashMap<(usize, usize), Vec<(usize, usize)>> = HashMap::new();

    for (position, _) in nodes {
        neighbours.insert(*position, get_neighbours(*position, nodes, input));
    }

    return neighbours;
}

fn get_neighbours(current: (usize, usize), nodes: &HashMap<(usize, usize), Node>, input: &Vec<usize>) -> Vec<(usize, usize)> {
    let mut neighbours: Vec<(usize, usize)> = Vec::new();
    
    for c in 0..input[1] {
        let pos: (usize, usize) = (current.0, c + 1);
        if pos == current { continue; }
        match nodes.get(&pos) {
            Some(n) => { neighbours.push(n.position); }
            None => {}
        }
    }
    for r in 0..input[0] {
        let pos: (usize, usize) = (r + 1, current.1);
        if pos == current { continue; }
        match nodes.get(&pos) {
            Some(n) => { neighbours.push(n.position); }
            None => {}
        }
    }

    return neighbours;
}

fn calculate_path(start: (usize, usize), goal: (usize, usize), mut nodes: HashMap<(usize, usize), Node>, neighbours: &HashMap<(usize, usize), Vec<(usize, usize)>>) -> i32 {
    let mut start_node: Node = *nodes.get_mut(&start).unwrap();
    start_node.heuristic = calculate_heuristic(start, goal);
    start_node.value = start_node.heuristic;
    *nodes.get_mut(&start).unwrap() = start_node;
    
    let mut open_list: BinaryHeap<Node> = BinaryHeap::from([start_node]);
    let mut open_set: HashSet<(usize, usize)> = HashSet::from([start]);
    let mut closed_set: HashSet<(usize, usize)> = HashSet::new();

    while open_set.len() > 0 {
        let current: Node = open_list.pop().unwrap();
        open_set.remove(&current.position);

        if current.position == goal {
            return count_path(current, &nodes);
        }
        closed_set.insert(current.position);

        for neighbour in neighbours.get(&current.position).unwrap() {
            if closed_set.contains(&neighbour) { continue; }

            let mut neighbour_node: Node = *nodes.get_mut(&neighbour).unwrap();
            let cost = current.cost + 1;

            if !open_set.contains(&neighbour) {
                neighbour_node.update(&current, goal);
                open_list.push(neighbour_node);
                open_set.insert(neighbour_node.position);
            } else if cost < neighbour_node.cost {
                neighbour_node.update(&current, goal);
            }

            *nodes.get_mut(&neighbour).unwrap() = neighbour_node;
        }
    }

    return -1;
}

fn calculate_heuristic(current: (usize, usize), goal: (usize, usize)) -> usize {
    if current.0 != goal.0 && current.1 != goal.1 {
        return 2;
    } else if current == goal {
        return 0;
    } else {
        return 1;
    }
}

fn count_path(goal_node: Node, nodes: &HashMap<(usize, usize), Node>) -> i32 {
    let mut current: Node = goal_node;

    let mut count: i32 = 0;
    while let Some((r, c)) = current.parent {
        count += 1;
        current = *nodes.get(&(r, c)).unwrap();
    }

    return count;
}

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