Hypyt

use std::collections::VecDeque;
use std::io::{BufRead, Write, stdin, stdout};

fn read_next<'a, I>(iter: &mut I) -> usize
where
    I: Iterator<Item = &'a str>,
{
    iter.next()
        .expect("invalid input")
        .parse::<usize>()
        .expect("invalid integer")
}

type Coords = (u8, u8);

struct Node {
    location: Coords,
    depth: u64,
    from_start: bool,
}

fn path_find(
    start: Coords,
    end: Coords,
    row_options: &Vec<Vec<Coords>>,
    col_options: &Vec<Vec<Coords>>,
    x_len: usize,
    y_len: usize,
) -> Option<u64> {
    if start == end {
        return Some(0);
    }

    let mut search_queue: VecDeque<Node> = VecDeque::from([
        Node {
            location: start,
            depth: 0,
            from_start: true,
        },
        Node {
            location: end,
            depth: 0,
            from_start: false,
        },
    ]);
    let mut dist_begin: Vec<Vec<u64>> = vec![vec![u64::MAX; x_len]; y_len];
    dist_begin[start.1 as usize][start.0 as usize] = 0;
    let mut dist_end: Vec<Vec<u64>> = vec![vec![u64::MAX; x_len]; y_len];
    dist_end[end.1 as usize][end.0 as usize] = 0;

    while let Some(node) = search_queue.pop_front() {
        // Possible next directions
        for next in [
            &row_options[node.location.1 as usize],
            &col_options[node.location.0 as usize],
        ] {
            for el in next {
                if *el == node.location {
                    continue;
                }
                let value = node.depth + 1;
                if node.from_start {
                    if dist_end[el.1 as usize][el.0 as usize] != u64::MAX {
                        return Some(value + dist_end[el.1 as usize][el.0 as usize]);
                    }
                    if dist_begin[el.1 as usize][el.0 as usize] == u64::MAX {
                        search_queue.push_back(Node {
                            location: *el,
                            depth: value,
                            from_start: node.from_start,
                        });
                        dist_begin[el.1 as usize][el.0 as usize] = value;
                    }
                } else {
                    if dist_begin[el.1 as usize][el.0 as usize] != u64::MAX {
                        return Some(value + dist_begin[el.1 as usize][el.0 as usize]);
                    }
                    if dist_end[el.1 as usize][el.0 as usize] == u64::MAX {
                        search_queue.push_back(Node {
                            location: *el,
                            depth: value,
                            from_start: node.from_start,
                        });
                        dist_end[el.1 as usize][el.0 as usize] = value;
                    }
                }
            }
        }
    }
    None
}

fn main() {
    let mut input = stdin().lock();
    let mut nmq = String::new();
    input.read_line(&mut nmq).expect("failed to read line");
    let mut nmq = nmq.split_ascii_whitespace();
    let n = read_next(&mut nmq) as u8;
    let m = read_next(&mut nmq) as u8;
    let q = read_next(&mut nmq) as u32;

    let mut grid: Vec<Vec<bool>> = vec![vec![false; m as usize]; n as usize];
    for y in 0..n {
        let mut line = String::new();
        input.read_line(&mut line).expect("failed to read line");
        for (x, chr) in line.trim().chars().enumerate() {
            grid[y as usize][x as usize] = chr == '.';
        }
    }

    let mut options_per_row: Vec<Vec<Coords>> = vec![Vec::new(); n as usize];
    let mut options_per_col: Vec<Vec<Coords>> = vec![Vec::new(); m as usize];
    for (y, row) in grid.iter().enumerate() {
        for (x, allowed) in row.iter().enumerate() {
            if *allowed {
                options_per_row[y].push((x as u8, y as u8));
                options_per_col[x].push((x as u8, y as u8));
            }
        }
    }

    let mut xys = String::with_capacity(8);
    let mut lock = stdout().lock();
    for _ in 0..q {
        input.read_line(&mut xys).expect("failed to read line");
        let mut split = xys.split_ascii_whitespace();
        let y1 = (read_next(&mut split) - 1) as u8;
        let x1 = (read_next(&mut split) - 1) as u8;
        let y2 = (read_next(&mut split) - 1) as u8;
        let x2 = (read_next(&mut split) - 1) as u8;

        let _ = match path_find(
            (x1, y1),
            (x2, y2),
            &options_per_row,
            &options_per_col,
            m as usize,
            n as usize,
        ) {
            Some(i) => writeln!(lock, "{}", i),
            None => writeln!(lock, "-1"),
        };
        xys.clear();
    }
}

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: TIME LIMIT EXCEEDED

Test 25

Group: 5

Verdict: ACCEPTED

Test 26

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 27

Group: 5

Verdict: ACCEPTED