Hypyt

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

warning: unused variable: `l`
  --> input/code.rs:26:13
   |
26 |         for l in 0..m {
   |             ^ help: if this is intentional, prefix it with an underscore: `_l`
   |
   = note: `#[warn(unused_variables)]` on by default

warning: unused variable: `l`
   --> input/code.rs:101:13
    |
101 |         for l in 0..node_count {
    |             ^ help: if this is intentional, prefix it with an underscore: `_l`

warning: type alias `Pos` is never used
 --> input/code.rs:4:6
  |
4 | type Pos = (usize, usize);
  |      ^^^
  |
  = note: `#[warn(dead_code)]` on by default

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

warning: function `two_jump_gap` is never used
   --> input/code.rs:185:4
    |
185 | fn two_jump_ga...

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

fn main() {
    //test_perf();
    //from_file();
    //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: Vec<Vec<bool>> = vec![];

    for i in 0..n {
        board.push(vec![]);
        input.clear();
        _ = stdin.read_line(&mut input);
        let mut line = input.chars();

        for l in 0..m {
            board[i].push(line.next().unwrap() == '*');
        }
    }

    //let mut tests: Vec<(usize, usize, usize, usize)> = vec![];

    let distance_pairs = precomputations(&board, n, m);

    let mut results = 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));

        results.push(process_test(
            &board,
            n,
            &distance_pairs,
            (y1 - 1, x1 - 1, y2 - 1, x2 - 1),
        ));
    }
    for r in results {
        print!("{r} ");
    }
    // test_once(
    //     &tests, &board, &row_safe, &col_safe, &mut cells, n, m, is_sparse,
    // );
}

fn precomputations(board: &Vec<Vec<bool>>, n: usize, m: usize) -> Vec<Vec<i32>> {
    let mut cols_in_row: Vec<Vec<usize>> = vec![];
    cols_in_row.reserve(n);
    let mut rows_in_col: Vec<Vec<usize>> = vec![];
    rows_in_col.reserve(m);
    for _ in 0..m {
        rows_in_col.push(vec![]);
    }
    for i in 0..n {
        let row = &board[i];
        cols_in_row.push(vec![]);
        for l in 0..m {
            let cell = row[l];
            if !cell {
                cols_in_row[i].push(l);
                rows_in_col[l].push(i);
            }
        }
    }
    let node_count = n + m;
    let mut connections: Vec<Vec<usize>> = vec![];
    for _ in 0..node_count {
        connections.push(vec![]);
    }

    for i in 0..n {
        for &l in &cols_in_row[i] {
            let row_index = i;
            let col_index = n + l;

            connections[row_index].push(col_index);
            connections[col_index].push(row_index);
        }
    }

    let mut distance_pairs: Vec<Vec<i32>> = vec![];

    for i in 0..node_count {
        distance_pairs.push(vec![]);
        for l in 0..node_count {
            distance_pairs[i].push(-1);
        }
    }

    let mut deque: VecDeque<usize> = VecDeque::new();

    for s in 0..node_count {
        if connections[s].is_empty() {
            distance_pairs[s][s] = 0;
            continue;
        }

        let dist_row = &mut distance_pairs[s];
        dist_row[s] = 0;
        deque.clear();
        deque.push_back(s);

        while deque.len() > 0 {
            let u = deque.pop_back().unwrap();
            let nu = dist_row[u] + 1;
            for &v in &connections[u] {
                if dist_row[v] == -1 {
                    dist_row[v] = nu;
                    deque.push_back(v);
                }
            }
        }
    }
    distance_pairs
}

const START_MIN: i32 = 67i32.pow(5);

fn process_test(
    board: &Vec<Vec<bool>>,
    n: usize,
    distance_pairs: &Vec<Vec<i32>>,
    test: (usize, usize, usize, usize),
) -> i32 {
    let a = (test.0, test.1);
    let b = (test.2, test.3);

    if board[a.0][a.1] || board[b.0][b.1] {
        return -1;
    }
    if a == b {
        return 0;
    }
    /*if one_jump_gap(&a, &b) {
        return 1;}
    if two_jump_gap(board, &a, &b) {
        return 2;
    }*/

    let start_row = a.0;
    let end_row = b.0;
    let start_col = n + a.1;
    let end_col = n + b.1;

    let mut smallest_distance = START_MIN;

    let mut res_distances = vec![];
    res_distances.push(distance_pairs[start_row][end_row]);
    res_distances.push(distance_pairs[start_row][end_col]);
    res_distances.push(distance_pairs[start_col][end_row]);
    res_distances.push(distance_pairs[start_col][end_col]);

    let mut found = false;

    for dist in res_distances {
        if dist != -1 && dist < smallest_distance {
            smallest_distance = dist;
            found = true;
        }
    }

    if !found { -1 } else { smallest_distance + 1 }
}

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

fn two_jump_gap(board: &Vec<Vec<bool>>, 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: WRONG ANSWER

Test 5

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

Test 6

Group: 2, 5

Verdict: WRONG ANSWER

Test 7

Group: 2, 5

Verdict: WRONG ANSWER

Test 8

Group: 2, 5

Verdict: WRONG ANSWER

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

Test 20

Group: 5

Verdict: ACCEPTED

Test 21

Group: 5

Verdict: ACCEPTED

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