Hypyt

use std::collections::{HashMap, VecDeque};
use std::io::{self, BufRead, Write};

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")
}

struct Node {
    location: (u8, u8),
    depth: u64,
}

fn path_find(
    start: (u8, u8),
    end: (u8, u8),
    row_options: &Vec<Vec<(u8, u8)>>,
    col_options: &Vec<Vec<(u8, u8)>>,
    x_len: usize,
    y_len: usize,
    cache: &mut HashMap<u32, u64>,
) -> Option<u64> {
    if start == end {
        return Some(0);
    }
    let hash_seed: u32 = (start.0 as u32)
        | (start.1 as u32) << 0x8
        | (end.0 as u32) << 0x10
        | (end.1 as u32) << 0x18;
    match cache.get(&hash_seed) {
        Some(i) => {
            return Some(*i);
        }
        None => {}
    }

    // Process layer-by-layer, add new to end
    let mut search_queue: VecDeque<Node> = VecDeque::from([Node {
        location: start,
        depth: 0,
    }]);
    let mut visited: Vec<Vec<bool>> = vec![vec![false; x_len]; y_len];
    visited[start.1 as usize][start.0 as usize] = true;

    loop {
        let search_path = match search_queue.pop_front() {
            Some(n) => n,
            None => break,
        };
        // Possible next directions
        for next in [
            &row_options[search_path.location.1 as usize],
            &col_options[search_path.location.0 as usize],
        ] {
            for el in next {
                if *el == search_path.location {
                    continue;
                }
                if *el == end {
                    cache.insert(hash_seed, search_path.depth + 1);
                    return Some(search_path.depth + 1);
                }
                if *el != search_path.location && !visited[el.1 as usize][el.0 as usize] {
                    search_queue.push_back(Node {
                        location: *el,
                        depth: search_path.depth + 1,
                    });
                    visited[el.1 as usize][el.0 as usize] = true;
                }
            }
        }
    }
    None
}

fn main() {
    let mut input = io::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 == '.';
        }
    }

    // Pre-populate options
    let mut options_per_row: Vec<Vec<(u8, u8)>> = vec![Vec::new(); n as usize];
    let mut options_per_col: Vec<Vec<(u8, u8)>> = 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 cache: HashMap<u32, u64> = HashMap::new();
    let mut xys = String::with_capacity(8);
    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 mut lock = io::stdout().lock();
        let _ = match path_find(
            (x1, y1),
            (x2, y2),
            &options_per_row,
            &options_per_col,
            m as usize,
            n as usize,
            &mut cache,
        ) {
            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: 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: TIME LIMIT EXCEEDED

Test 27

Group: 5

Verdict: ACCEPTED