Hypyt

use std::cmp::Ordering;
use std::{
    collections::{BinaryHeap, HashMap},
    io,
};
type Pos = (usize, usize);
fn main() {
    let mut input = String::new();
    let stdin = io::stdin();
    _ = stdin.read_line(&mut input);
    let mut first_line = input.split_whitespace();
    let n: usize = first_line.next().unwrap().parse().unwrap();
    let m: usize = first_line.next().unwrap().parse().unwrap();
    let q: usize = first_line.next().unwrap().parse().unwrap();

    let mut board: Vec<Vec<bool>> = vec![];

    for _ in 0..n {
        input.clear();
        _ = stdin.read_line(&mut input);
        let mut line = input.chars();

        let mut vec = vec![];

        for _ in 0..m {
            vec.push(line.next().unwrap() == '*');
        }

        board.push(vec);
    }

    let mut tests: Vec<(usize, usize, usize, usize)> = vec![];

    for _ in 0..q {
        input.clear();
        _ = stdin.read_line(&mut input);
        let mut line = input.split_whitespace();
        let y1: usize = line.next().unwrap().parse().unwrap();
        let x1: usize = line.next().unwrap().parse().unwrap();
        let y2: usize = line.next().unwrap().parse().unwrap();
        let x2: usize = line.next().unwrap().parse().unwrap();
        tests.push((y1 - 1, x1 - 1, y2 - 1, x2 - 1));
    }

    for t in tests {
        let start = (t.0, t.1);
        let end = (t.2, t.3);
        println!("{}", a_star(&board, start, end).len() as i32 - 1);
    }
}

fn a_star(board: &Vec<Vec<bool>>, start: Pos, end: Pos) -> Vec<Pos> {
    let mut open_set: BinaryHeap<AStarTile> = BinaryHeap::from([AStarTile {
        cost: 0,
        position: start,
    }]);

    let mut came_from: HashMap<Pos, Pos> = HashMap::new();

    let mut g_score: HashMap<Pos, usize> = HashMap::new();
    g_score.insert(start, 0);

    let mut f_score: HashMap<Pos, usize> = HashMap::new();
    f_score.insert(start, heuristic(start, end));

    while open_set.len() > 0 {
        let current: Pos = open_set.pop().unwrap().position;
        if current == end {
            return get_res_path(&came_from, current);
        }
        for neighbor in get_neighbors(&current, &board) {
            let tentative_score = g_score.get(&current).unwrap_or(&usize::MAX) + 1;
            if tentative_score < *g_score.get(&neighbor).unwrap_or(&usize::MAX) {
                came_from.insert(neighbor, current);
                g_score.insert(neighbor, tentative_score);
                let score_f = tentative_score + heuristic(neighbor, end);
                f_score.insert(neighbor, score_f);
                open_set.push(AStarTile {
                    cost: score_f,
                    position: neighbor,
                });
            }
        }
    }

    return vec![]; //no path found
}

fn get_neighbors(pos: &Pos, board: &Vec<Vec<bool>>) -> Vec<Pos> {
    let mut res: Vec<Pos> = vec![];
    let n = board.len();
    let m = board[0].len();
    for i in 0..n {
        if i == pos.0 {
            continue;
        }
        if !board[i][pos.1] {
            res.push((i, pos.1));
        }
    }
    for i in 0..m {
        if i == pos.1 {
            continue;
        }
        if !board[pos.0][i] {
            res.push((pos.0, i));
        }
    }
    res
}

fn get_res_path(came_from: &HashMap<Pos, Pos>, mut current: Pos) -> Vec<Pos> {
    let mut res: Vec<Pos> = vec![current];

    loop {
        if let Some(prev) = came_from.get(&current) {
            current = *prev;
            res.push(current);
        } else {
            break;
        }
    }
    res.reverse();
    res
}

fn heuristic(start: Pos, end: Pos) -> usize {
    start.0.abs_diff(end.0) + start.1.abs_diff(end.1)
}

#[derive(Copy, Clone, Eq, PartialEq)]
struct AStarTile {
    cost: usize,
    position: Pos,
}
impl PartialOrd for AStarTile {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}
impl Ord for AStarTile {
    fn cmp(&self, other: &Self) -> Ordering {
        other
            .cost
            .cmp(&self.cost)
            .then_with(|| self.position.cmp(&other.position))
    }
}

Test 1 (public)

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

Test 2

Group: 1, 2, 3, 4, 5

Verdict: WRONG ANSWER

Test 3

Group: 1, 2, 3, 4, 5

Verdict: WRONG ANSWER

Test 4

Group: 1, 2, 3, 4, 5

Verdict: WRONG ANSWER

Test 5

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

Test 6

Group: 2, 5

Verdict: WRONG ANSWER

Test 7

Group: 2, 5

Verdict: WRONG ANSWER

Test 8

Group: 2, 5

Verdict: WRONG ANSWER

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