Hypyt

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

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

warning: 2 warnings emitted

// use rand::random; //random for test generation
use std::io;
use std::time::*;
type Pos = (usize, usize);
use std::thread;
use std::time::Duration;
fn main() {
    // print_random_test(250, 250, 100);
    // 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 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();

    let mut threads = 1;

    if q >= 100000 {
        threads = 2;
    }

    //let mut test_iterator = tests.iter();

    let mut handles = vec![];
    for thread_index in 0..threads {
        let clone_board = board.clone();
        let mut thread_tests = vec![];
        //println!("{q}, {threads}");
        if thread_index != threads - 1 {
            for _ in 0..(q / threads) {
                thread_tests.push(tests.pop().unwrap());
                //println!("aa");
            }
        } else {
            for _ in 0..tests.len() {
                thread_tests.push(tests.pop().unwrap());
                //println!("aa");
            }
        }
        //println!("{}", thread_tests.len());
        handles.push(thread::spawn(move || {
            let mut thread_res = vec![];
            // let start_i = i * thread_tests.len() / threads;
            // let end_i = (i + 1) * thread_tests.len() / threads;
            for t in thread_tests {
                let start = (t.0, t.1);
                let end = (t.2, t.3);

                let res = breadth_first(&clone_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()
                //     );
                // }

                thread_res.push(res);
            }
            thread_res
        }));
    }
    for h in handles {
        if let Ok(res) = h.join() {
            for r in res.iter().rev() {
                println!("{r}");
            }
        } else {
            println!("thread failed");
        }
    }

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

// fn print_random_test(n: usize, m: usize, q: usize) {
//     println!("{n} {m} {q}");
//     let mut open: Vec<Pos> = vec![];
//     for i in 0..n {
//         for l in 0..m {
//             let monster: bool = random();
//             if monster {
//                 print!("*");
//             } else {
//                 print!(".");
//                 open.push((i, l));
//             }
//         }
//         println!();
//     }
//     for _ in 0..q {
//         let a = open[random::<u32>() as usize % open.len()];
//         let b = open[random::<u32>() as usize % open.len()];
//         println!("{} {} {} {}", a.0 + 1, a.1 + 1, b.0 + 1, b.1 + 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: WRONG ANSWER

Test 10

Group: 3, 4, 5

Verdict: WRONG ANSWER

Test 11

Group: 3, 4, 5

Verdict: WRONG ANSWER

Test 12

Group: 4, 5

Verdict: WRONG ANSWER

Test 13

Group: 4, 5

Verdict: WRONG ANSWER

Test 14

Group: 4, 5

Verdict: WRONG ANSWER

Test 15

Group: 5

Verdict: WRONG ANSWER

Test 16

Group: 5

Verdict: WRONG ANSWER

Test 17

Group: 5

Verdict: WRONG ANSWER

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

Test 25

Group: 5

Verdict: WRONG ANSWER

Test 26

Group: 5

Verdict: WRONG ANSWER

Test 27

Group: 5

Verdict: ACCEPTED