Hypyt

warning: unused variable: `res`
  --> input/code.rs:89:17
   |
89 |             let res = breadth_first(&board, cells, start, end, n, m);
   |                 ^^^ help: if this is intentional, prefix it with an underscore: `_res`
   |
   = note: `#[warn(unused_variables)]` on by default

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

warning: function `test_once` is never used
  --> input/code.rs:58:4
   |
58 | fn test_once(
   |    ^^^^^^^^^

warning: 3 warnings emitted

use std::collections::VecDeque;
use std::io;
use std::time::*;
type Pos = (usize, usize);

fn test_perf() {
    let start_time = SystemTime::now();
    for _ in 0..(2 * 10usize.pow(5)) {
        let mut cells: VecDeque<Pos> = vec![(0, 0)].into();
        cells.reserve(250 + 250);
    }
    let dur = SystemTime::now().duration_since(start_time);
    println!("{:?}", dur.unwrap());
}

fn main() {
    //test_perf();
    //return;
    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 cells: VecDeque<Pos> = vec![].into();
    cells.reserve(n + m);

    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));
    }
    //test_once(&tests, &board, &mut cells, n, m);
    test_many(&tests, &board, &mut cells, n, m);
}

fn test_once(
    tests: &Vec<(usize, usize, usize, usize)>,
    board: &[[bool; 250]; 250],
    cells: &mut VecDeque<Pos>,
    n: usize,
    m: usize,
) {
    for t in tests {
        let start = (t.0, t.1);
        let end = (t.2, t.3);

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

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

fn test_many(
    tests: &Vec<(usize, usize, usize, usize)>,
    board: &[[bool; 250]; 250],
    cells: &mut VecDeque<Pos>,
    n: usize,
    m: usize,
) {
    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, cells, start, end, n, m);

            if i % 10000 == 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],
    cells: &mut VecDeque<Pos>,
    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;
    }
    cells.clear();
    cells.push_back(start);

    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;
    //let mut iters = 0;

    while cells.len() > 0 {
        let cell_len = cells.len();
        for _ in 0..cell_len {
            let cell = cells.pop_back().unwrap(); //.swap_remove(l);

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

            for i in (0..len).rev() {
                let col = cols[i];
                //iters += 1;
                if !board[cell.0][col] {
                    let new_cell = (cell.0, col);
                    if two_jump_gap(board, &new_cell, &end) {
                        //println!("iters: {iters}");
                        return jumps + 2;
                    }
                    cols.swap_remove(i);
                    cells.push_front(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: WRONG ANSWER

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

Test 6

Group: 2, 5

Verdict: TIME LIMIT EXCEEDED

Test 7

Group: 2, 5

Verdict: TIME LIMIT EXCEEDED

Test 8

Group: 2, 5

Verdict: TIME LIMIT EXCEEDED

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

Test 23

Group: 1, 2, 3, 4, 5

Verdict: WRONG ANSWER

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: TIME LIMIT EXCEEDED