Hypyt

warning: unused variable: `m`
  --> input/code.rs:91:13
   |
91 |     let (n, m, q): (usize, usize, usize) = {
   |             ^ help: if this is intentional, prefix it with an underscore: `_m`
   |
   = note: `#[warn(unused_variables)]` on by default

warning: 1 warning emitted

use std::{io, ops::BitAnd};

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
struct PathNode {
    jump_target: usize,
    jump_column: usize,
    path_length: usize,
}

#[derive(Debug, Clone, Eq)]
struct Row {
    first_half: u128,
    second_half: u128,
    pub paths: Vec<Option<PathNode>>, // (target row, jump column, path length)
}

impl PartialEq for Row {
    fn eq(&self, other: &Self) -> bool {
        self.first_half == other.first_half && self.second_half == other.second_half
    }
}
impl TryFrom<&Vec<bool>> for Row {
    type Error = ();

    fn try_from(value: &Vec<bool>) -> Result<Self, Self::Error> {
        match value.len() {
            len if len <= 128 => {
                let mut first_half = [false; 128];
                first_half[..len].copy_from_slice(&value);
                let first_half = u128_from_bits(first_half);
                let second_half = 0u128;
                Ok(Row {
                    first_half,
                    second_half,
                    paths: Vec::new(),
                })
            }
            len if len <= 256 => {
                let mut first_half = [false; 128];
                let mut second_half = [false; 128];
                first_half.copy_from_slice(&value[..128]);
                second_half.copy_from_slice(&value[128..]);
                let first_half = u128_from_bits(first_half);
                let second_half = u128_from_bits(second_half);
                Ok(Row {
                    first_half,
                    second_half,
                    paths: Vec::new(),
                })
            }
            _ => Err(()),
        }
    }
}
impl BitAnd for &Row {
    type Output = Row;

    fn bitand(self, rhs: Self) -> Self::Output {
        Row {
            first_half: self.first_half & rhs.first_half,
            second_half: self.second_half & rhs.second_half,
            paths: Vec::new(),
        }
    }
}
impl Row {
    fn is_zero(&self) -> bool {
        self.first_half == 0 && self.second_half == 0
    }

    fn trailing_zeros(&self) -> u32 {
        let out = self.second_half.trailing_zeros();
        if out == 128 {
            out + self.first_half.trailing_zeros()
        } else {
            out
        }
    }
}
fn u128_from_bits(value: [bool; 128]) -> u128 {
    let mut out = 0u128;
    for i in 0..128 {
        out += (value[i] as u128) << 127 - i;
    }
    out
}

fn main() {
    let mut input = String::new();
    io::stdin().read_line(&mut input).unwrap();
    let (n, m, q): (usize, usize, usize) = {
        let mut iter = input.split_whitespace();
        (
            iter.next().unwrap().parse().unwrap(),
            iter.next().unwrap().parse().unwrap(),
            iter.next().unwrap().parse().unwrap(),
        )
    };
    let mut map: Vec<Vec<bool>> = Vec::new();
    for _ in 0..n {
        let mut input = String::new();
        io::stdin().read_line(&mut input).unwrap();
        map.push(input.trim().chars().map(|x| x == '.').collect());
    }

    let mut rows: Vec<Row> = map.iter().map(|row| row.try_into().unwrap()).collect();

    for target_row in 0..n {
        for row in rows.iter_mut() {
            row.paths.push(None);
        }

        for row in 0..n {
            let intersection = &rows[row] & &rows[target_row];
            if !intersection.is_zero() {
                rows[row].paths[target_row] = Some(PathNode {
                    jump_target: target_row,
                    jump_column: (255 - intersection.trailing_zeros()) as usize,
                    path_length: 1,
                });
            }
        }

        for step in 1..n {
            let mut can_continue = false;
            for step_target_row in 0..n {
                if rows[step_target_row].paths[target_row].is_some_and(|x| x.path_length == step) {
                    for row in 0..n {
                        if rows[row].paths[target_row].is_none() {
                            let intersection = &rows[row] & &rows[step_target_row];
                            if !intersection.is_zero() {
                                rows[row].paths[target_row] = Some(PathNode {
                                    jump_target: step_target_row,
                                    jump_column: (255 - intersection.trailing_zeros()) as usize,
                                    path_length: step + 1,
                                });
                                can_continue = true;
                            }
                        }
                    }
                }
            }
            if !can_continue {
                break;
            }
        }
    }

    let mut queries: Vec<((usize, usize), (usize, usize))> = Vec::new();
    for _ in 0..q {
        let mut input = String::new();
        io::stdin().read_line(&mut input).unwrap();
        let (y1, x1, y2, x2): (usize, usize, usize, usize) = {
            let mut iter = input.split_whitespace();

            let y1 = iter.next().unwrap().parse::<usize>().unwrap() - 1;
            let x1 = iter.next().unwrap().parse::<usize>().unwrap() - 1;
            let y2 = iter.next().unwrap().parse::<usize>().unwrap() - 1;
            let x2 = iter.next().unwrap().parse::<usize>().unwrap() - 1;

            (y1, x1, y2, x2)
        };
        queries.push(((x1, y1), (x2, y2)));
    }

    let rows = rows;
    let queries = queries;
    let map = map;

    for query in queries {
        println!("{}", process_query(&rows, &map, query));
    }
}

fn process_query(
    rows: &Vec<Row>,
    map: &Vec<Vec<bool>>,
    query: ((usize, usize), (usize, usize)),
) -> i32 {
    if query.0 == query.1 {
        return 0;
    }
    if query.0.0 == query.1.0 || query.0.1 == query.1.1 {
        return 1;
    }
    if rows[query.0.1].paths[query.1.1].is_none() {
        return -1;
    }
    if rows[query.0.1].paths[query.1.1].unwrap().jump_target == query.1.1
        && (map[query.0.1][query.1.0] || map[query.1.1][query.0.0])
    {
        return 2;
    }

    let mut steps = 0;
    if !map[rows[query.0.1].paths[query.1.1].unwrap().jump_target][query.0.0] {
        steps += 1;
    }
    let mut current_row = query.0.1;

    while rows[current_row].paths[query.1.1].unwrap().jump_target != query.1.1 {
        current_row = rows[current_row].paths[query.1.1].unwrap().jump_target;
        steps += 2;
    }

    steps += 1;
    if !map[current_row][query.1.0] {
        steps += 1;
    }
    steps
}

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

thread 'main' panicked at input/code.rs:42:29:
source slice length (122) does not match destination slice length (128)
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

Test 7

Group: 2, 5

Verdict: RUNTIME ERROR

thread 'main' panicked at input/code.rs:42:29:
source slice length (122) does not match destination slice length (128)
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

Test 8

Group: 2, 5

Verdict: RUNTIME ERROR

thread 'main' panicked at input/code.rs:42:29:
source slice length (122) does not match destination slice length (128)
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

Test 9

Group: 3, 4, 5

Verdict: ACCEPTED

Test 10

Group: 3, 4, 5

Verdict: ACCEPTED

Test 11

Group: 3, 4, 5

Verdict: WRONG ANSWER

Test 12

Group: 4, 5

Verdict: ACCEPTED

Test 13

Group: 4, 5

Verdict: ACCEPTED

Test 14

Group: 4, 5

Verdict: WRONG ANSWER

Test 15

Group: 5

Verdict: RUNTIME ERROR

thread 'main' panicked at input/code.rs:42:29:
source slice length (122) does not match destination slice length (128)
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

Test 16

Group: 5

Verdict: RUNTIME ERROR

thread 'main' panicked at input/code.rs:42:29:
source slice length (122) does not match destination slice length (128)
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

Test 17

Group: 5

Verdict: RUNTIME ERROR

thread 'main' panicked at input/code.rs:42:29:
source slice length (122) does not match destination slice length (128)
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

Test 18

Group: 5

Verdict: RUNTIME ERROR

thread 'main' panicked at input/code.rs:42:29:
source slice length (122) does not match destination slice length (128)
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

Test 19

Group: 5

Verdict: RUNTIME ERROR

thread 'main' panicked at input/code.rs:42:29:
source slice length (122) does not match destination slice length (128)
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

Test 20

Group: 5

Verdict: RUNTIME ERROR

thread 'main' panicked at input/code.rs:42:29:
source slice length (122) does not match destination slice length (128)
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

Test 21

Group: 5

Verdict: RUNTIME ERROR

thread 'main' panicked at input/code.rs:42:29:
source slice length (122) does not match destination slice length (128)
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

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

thread 'main' panicked at input/code.rs:42:29:
source slice length (122) does not match destination slice length (128)
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

Test 26

Group: 5

Verdict: RUNTIME ERROR

thread 'main' panicked at input/code.rs:42:29:
source slice length (122) does not match destination slice length (128)
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

Test 27

Group: 5

Verdict: RUNTIME ERROR

thread 'main' panicked at input/code.rs:42:29:
source slice length (122) does not match destination slice length (128)
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace