Hypyt

warning: unused import: `std::cmp::Ordering`
 --> input/code.rs:1:5
  |
1 | use std::cmp::Ordering;
  |     ^^^^^^^^^^^^^^^^^^
  |
  = note: `#[warn(unused_imports)]` on by default

warning: unused imports: `BinaryHeap`, `HashMap`
 --> input/code.rs:3:19
  |
3 |     collections::{BinaryHeap, HashMap},
  |                   ^^^^^^^^^^  ^^^^^^^

warning: function `debug_print` is never used
   --> input/code.rs:156:4
    |
156 | fn debug_print(
    |    ^^^^^^^^^^^
    |
    = note: `#[warn(dead_code)]` on by default

warning: 3 warnings emitted

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);
        println!("{}", test(&board, start, end));
    }
}

fn test(board: &Vec<Vec<bool>>, start: Pos, end: Pos) -> i32 {
    if start == end {
        return 0;
    }

    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 open_rows: Vec<usize> = vec![start.0];
    let mut open_cols: Vec<usize> = vec![start.1];
    // debug_print(
    //     board,
    //     &reached_rows,
    //     &reached_cols,
    //     &open_rows,
    //     &open_cols,
    //     &start,
    //     &end,
    // );
    while open_rows.len() + open_cols.len() > 0 {
        //println!("rows: {open_rows:#?}");
        //println!("cols: {open_cols:#?}");
        hops += 1;
        let mut new_open_cols = vec![];
        for r in &open_rows {
            let mut cols: Vec<usize> = get_cols(*r, end, board, &reached_cols);
            for c in &cols {
                reached_cols[*c] = true;
                if (*r, *c) == end {
                    return hops;
                }
            }
            new_open_cols.append(&mut cols);
        }
        open_rows.clear();
        for c in &open_cols {
            let mut rows: Vec<usize> = get_rows(*c, end, board, &reached_rows);
            for r in &rows {
                reached_rows[*r] = true;
                if (*r, *c) == end {
                    return hops;
                }
            }
            open_rows.append(&mut rows);
        }
        open_cols = new_open_cols;
        // debug_print(
        //     board,
        //     &reached_rows,
        //     &reached_cols,
        //     &open_rows,
        //     &open_cols,
        //     &start,
        //     &end,
        // );
    }

    -1
}

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

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

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

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

    for (i, r) in board[start_row].iter().enumerate() {
        if !*r && !reached_cols[i] {
            res.push(i);
        }
    }
    res
}

fn debug_print(
    board: &Vec<Vec<bool>>,
    reached_rows: &Vec<bool>,
    reached_cols: &Vec<bool>,
    open_rows: &Vec<usize>,
    open_cols: &Vec<usize>,
    start: &Pos,
    end: &Pos,
) {
    //print reached cols
    print!("  ");
    for c in reached_cols {
        if *c {
            print!("■ ");
        } else {
            print!("□ ");
        }
    }
    println!();

    //print board and reached rows
    for (i, row) in board.iter().enumerate() {
        let open_row = open_rows.contains(&i);
        if reached_rows[i] {
            print!("■ ");
        } else {
            print!("□ ");
        }

        for (l, cell) in row.iter().enumerate() {
            if start.0 == i && start.1 == l {
                print!("S ");
            } else if end.0 == i && end.1 == l {
                print!("E ");
            } else {
                if open_row || open_cols.contains(&l) {
                    if *cell {
                        print!("▣ ");
                    } else {
                        print!("▢ ");
                    }
                } else {
                    if *cell {
                        print!("▪ ");
                    } else {
                        print!("  ");
                    }
                }
            }
        }
        println!();
    }
    println!();
}

// 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;
//                 //if !openset_contains(&open_set, tile) {
//                 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.position == item.position {
//             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 += 1;
//     }
//     if start.1 != end.1 {
//         res += 1;
//     }
//     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