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: variable `iters` is assigned to, but never used
   --> input/code.rs:106:13
    |
106 |     let mut iters = 0;
    |             ^^^^^
    |
    = note: consider using `_iters` instead
    = note: `#[warn(unused_variables)]` on by default

warning: unused variable: `m`
   --> input/code.rs:264:71
    |
264 | fn get_rows_a(start_col: usize, board: &[[bool; 250]; 250], n: usize, m: usize) -> Vec<Pos> {
    |                                                                       ^ help: if this is intentional, prefix it with an underscore: `_m`

warning: unused variable: `n`
   --> input/code.rs:274:61
    |
274 | fn get_cols_a(start_row: us...

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: [[bool; 250]; 250] = [[false; 250]; 250];

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

        for l in 0..m {
            board[i][l] = line.next().unwrap() == '*';
        }
    }

    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));
    }

    let mut board_rows_free = [0u8; 250];
    let mut board_cols_free = [0u8; 250];
    for i in 0..n {
        for l in 0..m {
            if !board[i][l] {
                board_rows_free[i] += 1;
                board_cols_free[l] += 1;
            }
        }
    }

    //let mut cache: HashMap<(Pos, Pos), i32> = HashMap::new();

    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, n, m));
        // let key = (start, end);
        let res;
        // if cache.contains_key(&key) {
        //     res = *cache.get(&key).unwrap();
        // } else {
        res = test_alternate(&board, start, end, n, m, &board_rows_free, &board_cols_free);
        // cache.insert(key, res);
        // }

        println!("{res}");
    }
}

fn test_alternate(
    board: &[[bool; 250]; 250],
    start: Pos,
    end: Pos,
    n: usize,
    m: usize,
    board_rows_free: &[u8; 250],
    board_cols_free: &[u8; 250],
) -> i32 {
    if start == end {
        return 0;
    }

    if start.0 == end.0 || start.1 == end.1 {
        return 1;
    }

    let mut jumps = 2;
    let mut open_start: Vec<Pos> = vec![start];
    let mut open_end: Vec<Pos> = vec![end];

    let mut reached_rows = [false; 250];
    let mut reached_cols = [false; 250];
    // debug_print_alternate(
    //     board,
    //     &reached_rows,
    //     &reached_cols,
    //     &open_start,
    //     &open_end,
    //     &start,
    //     &end,
    //     n,
    //     m,
    // );
    let mut iters = 0;
    let mut peak_len = 0;

    loop {
        if open_start.len() == 0 || open_end.len() == 0 {
            //println!("iters: {iters}");
            break;
        }
        if open_start.len() > peak_len {
            peak_len = open_start.len();
        }
        if open_end.len() > peak_len {
            peak_len = open_end.len();
        }

        for a in 0..open_start.len() {
            let mut i = a;
            if a % 2 == 0 {
                i = open_start.len() - i - 1;
            }
            let pos_a = open_start[i];
            for b in 0..open_end.len() {
                let mut l = b;
                if b % 2 == 0 {
                    l = open_end.len() - l - 1;
                }
                let pos_b = open_end[l];
                iters += 1;
                if two_jump_gap(board, pos_a, pos_b) {
                    //println!("iters: {iters}");
                    //println!("peak: {peak_len}");
                    return jumps;
                }
            }
        }

        // for pos_a in &open_start {
        //     for pos_b in &open_end {
        //         iters += 1;
        //         if two_jump_gap(board, *pos_a, *pos_b) {
        //             println!("iters: {iters}");
        //             println!("peak: {peak_len}");
        //             return jumps;
        //         }
        //     }
        // }

        let start_pred_len = open_start.iter().fold(0, |acc, a| {
            acc + get_approx_next_pos_len(
                *a,
                &board_rows_free,
                &board_cols_free,
                &reached_rows,
                &reached_cols,
            )
        });
        let end_pred_len = open_end.iter().fold(0, |acc, a| {
            acc + get_approx_next_pos_len(
                *a,
                &board_rows_free,
                &board_cols_free,
                &reached_rows,
                &reached_cols,
            )
        });

        let end_smaller = start_pred_len > end_pred_len;

        let mut pos_less = &open_start;
        //let mut pos_more = &open_end;
        if end_smaller {
            pos_less = &open_end;
        }

        let mut new_pos_less = vec![];
        for p in pos_less {
            new_pos_less.append(&mut get_new_pos_vec(
                *p,
                board,
                &reached_rows,
                &reached_cols,
                n,
                m,
            ));
            reached_rows[p.0] = true;
            reached_cols[p.1] = true;
        }

        if end_smaller {
            open_end = new_pos_less;
        } else {
            open_start = new_pos_less;
        }

        jumps += 1;
        // debug_print_alternate(
        //     board,
        //     &reached_rows,
        //     &reached_cols,
        //     &open_start,
        //     &open_end,
        //     &start,
        //     &end,
        //     n,
        //     m,
        // );
    }

    -1
}

fn get_approx_next_pos_len(
    pos: Pos,
    board_rows_free: &[u8; 250],
    board_cols_free: &[u8; 250],
    reached_rows: &[bool; 250],
    reached_cols: &[bool; 250],
) -> usize {
    let res = if !reached_rows[pos.0] {
        board_rows_free[pos.0] as usize
    } else {
        0
    };
    res + if !reached_cols[pos.0] {
        board_cols_free[pos.1] as usize
    } else {
        0
    }
}

fn two_jump_gap(board: &[[bool; 250]; 250], a: Pos, b: Pos) -> bool {
    !board[a.0][b.1] || !board[b.0][a.1]
}

fn get_new_pos_vec(
    pos: Pos,
    board: &[[bool; 250]; 250],
    reached_rows: &[bool; 250],
    reached_cols: &[bool; 250],
    n: usize,
    m: usize,
) -> Vec<Pos> {
    let mut res = vec![];

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

    res
}

fn get_rows_a(start_col: usize, board: &[[bool; 250]; 250], n: usize, m: usize) -> Vec<Pos> {
    let mut res = vec![];

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

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

fn test(board: &[[bool; 250]; 250], start: Pos, end: Pos, n: usize, m: usize) -> 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()];

    let mut reached_rows = [false; 250];
    let mut reached_cols = [false; 250];

    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,
    // );
    // println!("rows: {open_rows:#?}");
    // println!("cols: {open_cols:#?}");
    let mut iters = 0;
    while open_rows.len() + open_cols.len() > 0 {
        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, n, m);
            for c in &cols {
                reached_cols[*c] = true;
                iters += 1;
                if (*r, *c) == end {
                    println!("iters {iters}");
                    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, n, m);
            for r in &rows {
                reached_rows[*r] = true;
                iters += 1;
                if (*r, *c) == end {
                    println!("iters {iters}");
                    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,
        // // );
        // println!("rows: {open_rows:#?}");
        // println!("cols: {open_cols:#?}");
    }

    -1
}

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

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

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

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

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

fn debug_print_alternate(
    board: &[[bool; 250]; 250],
    reached_rows: &[bool; 250],
    reached_cols: &[bool; 250],
    open_a: &Vec<Pos>,
    open_b: &Vec<Pos>,
    start: &Pos,
    end: &Pos,
    n: usize,
    m: usize,
) {
    //print reached cols
    print!("  ");
    for c in &reached_cols[0..m] {
        if *c {
            print!("■ ");
        } else {
            print!("□ ");
        }
    }
    println!();

    //print board and reached rows
    for (i, row) in board[0..n].iter().enumerate() {
        if reached_rows[i] {
            print!("■ ");
        } else {
            print!("□ ");
        }

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

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

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

Test 11

Group: 3, 4, 5

Verdict: WRONG ANSWER

Test 12

Group: 4, 5

Verdict: ACCEPTED

Test 13

Group: 4, 5

Verdict: ACCEPTED

Test 14

Group: 4, 5

Verdict: WRONG ANSWER

Test 15

Group: 5

Verdict: ACCEPTED

Test 16

Group: 5

Verdict: ACCEPTED

Test 17

Group: 5

Verdict: ACCEPTED

Test 18

Group: 5

Verdict: WRONG ANSWER

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