Hypyt

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

warning: unused import: `std::time`
 --> input/code.rs:3:5
  |
3 | use std::time;
  |     ^^^^^^^^^

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

warning: 3 warnings emitted

use std::collections::VecDeque;
use std::io;
use std::time;
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!(
                    "{} iter 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];

    /*let mut rows: [bool; 250] = [false; 250];
    let mut cols: [bool; 250] = [false; 250];*/
    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);
    if end.0 + 1 >= rows.len() {
        rows.swap_remove(start.0);
    } else {
        rows.swap_remove(end.0);
    }
    if end.1 + 1 >= cols.len() {
        cols.swap_remove(start.1);
    } else {
        cols.swap_remove(end.1);
    }

    let mut jumps = 1;

    while cells.len() > 0 {
        //let mut new_cells: Vec<Pos> = vec![];
        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);
                    //println!("{new_cell:?}");
                    if two_jump_gap(board, &new_cell, &end) {
                        return jumps + 2;
                    }
                    rows.swap_remove(i);
                    cells.push(new_cell);
                    //removed += 1;
                    //cols[cell.1] = true;
                }
            }
            let len = cols.len();
            //removed = 0;
            for i in (0..len).rev() {
                let col = cols[i];
                if !board[cell.0][col] {
                    let new_cell = (cell.0, col);
                    //println!("{new_cell:?}");
                    if two_jump_gap(board, &new_cell, &end) {
                        return jumps + 2;
                    }
                    //rows[cell.0] = true;
                    cols.swap_remove(i);
                    cells.push(new_cell);
                    //removed += 1;
                }
            }
        }

        //cells = new_cells;
        jumps += 1;
        //println!("{:?}", cells);
    }

    -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: RUNTIME ERROR

thread 'main' panicked at /build/rustc-kAv1jW/rustc-1.75.0+dfsg0ubuntu1~bpo0/library/alloc/src/vec/mod.rs:1458:13:
swap_remove index (is 39) should be < len (is 39)
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

Test 10

Group: 3, 4, 5

Verdict: RUNTIME ERROR

thread 'main' panicked at /build/rustc-kAv1jW/rustc-1.75.0+dfsg0ubuntu1~bpo0/library/alloc/src/vec/mod.rs:1458:13:
swap_remove index (is 39) should be < len (is 39)
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

Test 11

Group: 3, 4, 5

Verdict: RUNTIME ERROR

thread 'main' panicked at /build/rustc-kAv1jW/rustc-1.75.0+dfsg0ubuntu1~bpo0/library/alloc/src/vec/mod.rs:1458:13:
swap_remove index (is 39) should be < len (is 39)
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

Test 12

Group: 4, 5

Verdict: RUNTIME ERROR

thread 'main' panicked at /build/rustc-kAv1jW/rustc-1.75.0+dfsg0ubuntu1~bpo0/library/alloc/src/vec/mod.rs:1458:13:
swap_remove index (is 79) should be < len (is 79)
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

Test 13

Group: 4, 5

Verdict: RUNTIME ERROR

thread 'main' panicked at /build/rustc-kAv1jW/rustc-1.75.0+dfsg0ubuntu1~bpo0/library/alloc/src/vec/mod.rs:1458:13:
swap_remove index (is 79) should be < len (is 79)
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

Test 14

Group: 4, 5

Verdict: RUNTIME ERROR

thread 'main' panicked at /build/rustc-kAv1jW/rustc-1.75.0+dfsg0ubuntu1~bpo0/library/alloc/src/vec/mod.rs:1458:13:
swap_remove index (is 79) should be < len (is 79)
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

Test 15

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 16

Group: 5

Verdict: RUNTIME ERROR

thread 'main' panicked at /build/rustc-kAv1jW/rustc-1.75.0+dfsg0ubuntu1~bpo0/library/alloc/src/vec/mod.rs:1458:13:
swap_remove index (is 249) should be < len (is 249)
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

Test 17

Group: 5

Verdict: RUNTIME ERROR

thread 'main' panicked at /build/rustc-kAv1jW/rustc-1.75.0+dfsg0ubuntu1~bpo0/library/alloc/src/vec/mod.rs:1458:13:
swap_remove index (is 249) should be < len (is 249)
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

Test 18

Group: 5

Verdict: RUNTIME ERROR

thread 'main' panicked at /build/rustc-kAv1jW/rustc-1.75.0+dfsg0ubuntu1~bpo0/library/alloc/src/vec/mod.rs:1458:13:
swap_remove index (is 249) should be < len (is 249)
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

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