Hypyt

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

warning: 2 warnings emitted

use std::collections::VecDeque;
use std::io::{self};

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

        results.push(process_test(
            &board,
            n,
            &distance_pairs,
            (y1 - 1, x1 - 1, y2 - 1, x2 - 1),
        ));
    }
    for r in results {
        print!("{r} ");
    }
}

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_front().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 = 1000000000;

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

Test 10

Group: 3, 4, 5

Verdict: ACCEPTED

Test 11

Group: 3, 4, 5

Verdict: ACCEPTED

Test 12

Group: 4, 5

Verdict: ACCEPTED

Test 13

Group: 4, 5

Verdict: ACCEPTED

Test 14

Group: 4, 5

Verdict: ACCEPTED

Test 15

Group: 5

Verdict: ACCEPTED

Test 16

Group: 5

Verdict: ACCEPTED

Test 17

Group: 5

Verdict: ACCEPTED

Test 18

Group: 5

Verdict: ACCEPTED

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