Hypyt

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

warning: 1 warning emitted

use std::io;
use std::time::*;
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 start_time = SystemTime::now();

    // for i in 0..(2 * 10usize.pow(5)) {
    for t in &tests {
        let start = (t.0, t.1);
        let end = (t.2, t.3);

        let res = breadth_first(&board, start, end, n, m);

        // if i % 100 == 0 {
        //     let dur = SystemTime::now().duration_since(start_time);
        //     println!(
        //         "{} iters per second",
        //         (i as f32 / dur.unwrap().as_secs_f32()).round()
        //     );
        // }

        println!("{res}");
    }
    // }
    // let dur = SystemTime::now().duration_since(start_time);
    // println!("{:?}", dur.unwrap());
}

fn breadth_first(board: &[[bool; 250]; 250], start: Pos, end: Pos, n: usize, m: usize) -> i32 {
    if start == end {
        return 0;
    }
    if one_jump_gap(&start, &end) {
        return 1;
    }
    if two_jump_gap(board, &start, &end) {
        return 2;
    }

    let mut cells: Vec<Pos> = vec![start];
    cells.reserve(n * m / 4);

    let mut rows: Vec<usize> = (0..n).collect();
    let mut cols: Vec<usize> = (0..m).collect();

    rows.swap_remove(start.0);
    cols.swap_remove(start.1);

    let mut jumps = 1;

    while cells.len() > 0 {
        let cell_len = cells.len();
        for l in (0..cell_len).rev() {
            let cell = cells.swap_remove(l);

            let len = rows.len();
            for i in (0..len).rev() {
                let row = rows[i];
                if !board[row][cell.1] {
                    let new_cell = (row, cell.1);
                    if two_jump_gap(board, &new_cell, &end) {
                        return jumps + 2;
                    }
                    rows.swap_remove(i);
                    cells.push(new_cell);
                }
            }
            let len = cols.len();

            for i in (0..len).rev() {
                let col = cols[i];
                if !board[cell.0][col] {
                    let new_cell = (cell.0, col);
                    if two_jump_gap(board, &new_cell, &end) {
                        return jumps + 2;
                    }
                    cols.swap_remove(i);
                    cells.push(new_cell);
                }
            }
        }
        jumps += 1;
    }

    -1
}

fn one_jump_gap(a: &Pos, b: &Pos) -> bool {
    a.0 == b.0 || a.1 == b.1
}

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

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

Test 11

Group: 3, 4, 5

Verdict: ACCEPTED

Test 12

Group: 4, 5

Verdict: ACCEPTED

Test 13

Group: 4, 5

Verdict: ACCEPTED

Test 14

Group: 4, 5

Verdict: ACCEPTED

Test 15

Group: 5

Verdict: ACCEPTED

Test 16

Group: 5

Verdict: ACCEPTED

Test 17

Group: 5

Verdict: ACCEPTED

Test 18

Group: 5

Verdict: ACCEPTED

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