Hypyt

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

warning: function `breadth_first` is never used
   --> input/code.rs:123:4
    |
123 | fn breadth_first(board: &[[bool; 250]; 250], start: Pos, end: Pos, n: usize, m: usize) -> i32 {
    |    ^^^^^^^^^^^^^
    |
    = note: `#[warn(dead_code)]` on by default

warning: function `one_jump_gap` is never used
   --> input/code.rs:178:4
    |
178 | fn one_jump_gap(a: &Pos, b: &Pos) -> bool {
    |    ^^^^^^^^^^^^

warning: function `two_jump_gap` is never used
   --> input/code.rs:182:4
    |
182 | fn two_jump_gap(board: &[[bool; 250]; 250], a: &Pos, b: &Pos) -> bool {
    |    ^^^^^^^^^^^^

warning: 4 warnings emitted

use std::collections::VecDeque;
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 mut row_safe: Vec<Vec<usize>> = vec![Vec::new(); n];
    let mut col_safe: Vec<Vec<usize>> = vec![Vec::new(); m];

    for i in 0..n {
        for j in 0..m {
            if !board[i][j] {
                row_safe[i].push(j);
                col_safe[j].push(i);
            }
        }
    }
    // 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 = bread(start, end, n, m, &row_safe, &col_safe);

        // 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 bread(
    start: Pos,
    end: Pos,
    n: usize,
    m: usize,
    row_safe: &Vec<Vec<usize>>,
    col_safe: &Vec<Vec<usize>>,
) -> i32 {
    if start == end {
        return 0;
    }

    let mut visited = [[false; 250]; 250];
    visited[start.0][start.1] = true;

    let mut row_used = vec![false; n];
    let mut col_used = vec![false; m];
    let mut queue = VecDeque::new();
    queue.push_back((start, 0));

    while let Some(((r, c), dist)) = queue.pop_front() {
        if (r, c) == end {
            return dist;
        }

        if !row_used[r] {
            row_used[r] = true;
            for &cc in &row_safe[r] {
                if !visited[r][cc] {
                    visited[r][cc] = true;
                    queue.push_back(((r, cc), dist + 1));
                }
            }
        }

        if !col_used[c] {
            col_used[c] = true;
            for &rr in &col_safe[c] {
                if !visited[rr][c] {
                    visited[rr][c] = true;
                    queue.push_back(((rr, c), dist + 1));
                }
            }
        }
    }

    -1
}

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

    let mut rows: [bool; 250] = [false; 250];
    let mut cols: [bool; 250] = [false; 250];

    rows[start.0] = true;
    cols[start.1] = true;

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

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

            for col in 0..m {
                if !cols[col] && !board[cell.0][col] {
                    let new_cell = (cell.0, col);
                    if two_jump_gap(board, &new_cell, &end) {
                        return jumps + 2;
                    }
                    cols[col] = true;
                    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: 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: 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: TIME LIMIT EXCEEDED

Test 27

Group: 5

Verdict: ACCEPTED