Hypyt

warning: unreachable expression
  --> input/code.rs:66:5
   |
61 | /     loop {
62 | |         let rows = get_rows(pos, end, board);
63 | |         for i in rows {}
64 | |     }
   | |_____- any code following this expression is unreachable
65 |
66 |       -1
   |       ^^ unreachable expression
   |
   = note: `#[warn(unreachable_code)]` on by default

warning: unused variable: `hops`
  --> input/code.rs:59:13
   |
59 |     let mut hops = 0;
   |             ^^^^ help: if this is intentional, prefix it with an underscore: `_hops`
   |
   = note: `#[warn(unused_variables)]` on by default

warning: unused variable: `i`
  --> input/code.rs:63:13
   |
63 |         for i in rows {}
   |             ^ help: if this is intentional, prefix it with an underscore: `_i`

warning: variable does not need to be mutable
  --> input/code.rs:59:9
   |
59 |     let mut hops = 0;
   |         ----^^^^
   |         |
   |         help: remove this `mut`
   |
   = note: `#[warn(unused_mut)]` on by default...

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 test(board: &Vec<Vec<bool>>, start: Pos, end: Pos) -> i32 {
    let mut reached_rows: Vec<bool> = vec![false; board.len()];
    let mut reached_cols: Vec<bool> = vec![false; board[0].len()];

    reached_rows[start.0] = true;
    reached_cols[start.1] = true;

    let mut hops = 0;
    let mut pos: Pos = start;
    loop {
        let rows = get_rows(pos, end, board);
        for i in rows {}
    }

    -1
}

fn get_rows(start: Pos, end: Pos, board: &Vec<Vec<bool>>) -> Vec<usize> {
    let mut res = vec![];

    if board[end.0][start.1] {
        return vec![end.0];
    }

    for (i, r) in board.iter().enumerate() {
        if r[start.1] && start.0 != i {
            res.push(i);
        }
    }
    res
}
fn get_cols(start: Pos, end: Pos, board: &Vec<Vec<bool>>) -> Vec<usize> {
    let mut res = vec![];

    if board[start.0][end.1] {
        return vec![end.1];
    }

    for (i, r) in board[start.0].iter().enumerate() {
        if *r && start.1 != i {
            res.push(i);
        }
    }
    res
}

fn a_star(board: &Vec<Vec<bool>>, start: Pos, end: Pos) -> Vec<Pos> {
    // let mut reached_rows: Vec<bool> = vec![false; board.len()];
    // let mut reached_cols: Vec<bool> = vec![false; board[0].len()];

    // reached_rows[start.0] = true;
    // reached_cols[start.1] = true;

    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, &end) {
            if neighbor == end {
                came_from.insert(neighbor, current);
                return get_res_path(&came_from, neighbor);
            }
            // if reached_rows[neighbor.0] && reached_cols[neighbor.1] {
            //     continue;
            // }
            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);
                let tile = AStarTile {
                    cost: score_f,
                    position: neighbor,
                };

                // reached_rows[neighbor.0] = true;
                // reached_cols[neighbor.1] = true;
                open_set.push(tile);
            }
        }
    }

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

fn openset_contains(open_set: &BinaryHeap<AStarTile>, item: AStarTile) -> bool {
    for i in open_set {
        if *i == item {
            return true;
        }
    }
    false
}

fn get_neighbors(pos: &Pos, board: &Vec<Vec<bool>>, target: &Pos) -> Vec<Pos> {
    if pos.0 == target.0 || pos.1 == target.1 {
        return vec![*target];
    }
    let mut res: Vec<Pos> = vec![];
    let n = board.len();
    let m = board[0].len();
    let q1 = (pos.0, target.1);
    let q2 = (target.0, pos.1);
    if !board[q1.0][q1.1] {
        res.push(q1);
        return res;
    }
    if !board[q2.0][q2.1] {
        res.push(q2);
        return res;
    }
    for i in 0..n {
        if i == pos.0 || i == target.0 {
            continue;
        }
        if !board[i][pos.1] {
            res.push((i, pos.1));
        }
    }
    for i in 0..m {
        if i == pos.1 || i == target.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 {
    let mut res = 0;
    if start.0 != end.0 {
        res += 10;
    }
    if start.1 != end.1 {
        res += 10;
    }
    res
}

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

Test 7

Group: 2, 5

Verdict: ACCEPTED

Test 8

Group: 2, 5

Verdict: ACCEPTED

Test 9

Group: 3, 4, 5

Verdict: ACCEPTED

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

Test 25

Group: 5

Verdict: ACCEPTED

Test 26

Group: 5

Verdict: ACCEPTED

Test 27

Group: 5

Verdict: ACCEPTED