Hypyt

use std::collections::{HashMap, VecDeque};
use std::io;

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: (usize, usize),
    // Depth
    value: u64,
}

fn path_find(
    start: (usize, usize),
    end: (usize, usize),
    row_options: &Vec<Vec<(usize, usize)>>,
    col_options: &Vec<Vec<(usize, usize)>>,
    x_len: usize,
    y_len: usize,
    cache: &mut HashMap<((usize, usize), (usize, usize)), u64>
) -> Option<u64> {
    if start == end {
        return Some(0);
    }
    match cache.get(&(start, end)) {
        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,
        value: 0,
    }]);
    let mut visited: Vec<Vec<bool>> = vec![vec![false; x_len]; y_len];
    visited[start.1][start.0] = 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],
            &col_options[search_path.location.0],
        ] {
            for el in next {
                if *el == search_path.location {
                    continue;
                }
                if *el == end {
                    cache.insert((start, end), search_path.value + 1);
                    return Some(search_path.value + 1);
                }
                if *el != search_path.location && !visited[el.1][el.0] {
                    search_queue.push_back(Node {
                        location: *el,
                        value: search_path.value + 1,
                    });
                    visited[el.1][el.0] = true;
                }
            }
        }
    }
    None
}

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

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

    // Pre-populate options
    let mut options_per_row: Vec<Vec<(usize, usize)>> = vec![Vec::new(); n];
    let mut options_per_col: Vec<Vec<(usize, usize)>> = vec![Vec::new(); m];

    for (y, row) in grid.iter().enumerate() {
        for (x, allowed) in row.iter().enumerate() {
            if *allowed {
                options_per_row[y].push((x, y));
                options_per_col[x].push((x, y));
            }
        }
    }

    let mut cache: HashMap<((usize, usize), (usize, usize)), u64> = HashMap::new();
    for _ in 0..q {
        let mut xys = String::new();
        io::stdin()
            .read_line(&mut xys)
            .expect("failed to read line");
        let mut xys = xys.split_ascii_whitespace();
        let y1 = read_next(&mut xys) - 1;
        let x1 = read_next(&mut xys) - 1;
        let y2 = read_next(&mut xys) - 1;
        let x2 = read_next(&mut xys) - 1;
        match path_find((x1, y1), (x2, y2), &options_per_row, &options_per_col, m, n, &mut cache) {
            Some(i) => println!("{i}"),
            None => println!("-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: 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