Hypyt

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

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

struct Node {
    location: (u32, u32),
    // Depth
    value: u64,
}

// TODO: Persist route data between queries for optimization?
fn path_find(
    start: (u32, u32),
    end: (u32, u32),
    grid: &Vec<Vec<bool>>,
    options: &mut HashMap<(u32, u32), Vec<(u32, u32)>>,
) -> Option<u64> {
    if start == end {
        return Some(0);
    }

    // Process layer-by-layer, add new to end
    let mut search_queue: VecDeque<Node> = VecDeque::from([Node {
        location: start,
        value: 0,
    }]);
    // We'll terminate a search path if it visits some checked spot
    let mut visited: HashSet<(u32, u32)> = HashSet::from([start]);

    let y_len: u32 = grid.len().try_into().expect("invalid grid size");
    let x_len: u32 = grid[0].len().try_into().expect("invalid grid size");

    loop {
        let search_path = match search_queue.pop_front() {
            Some(n) => n,
            None => break,
        };
        // Possible next directions
        let next: Vec<(u32, u32)> = match options.get(&search_path.location) {
            Some(v) => v.to_owned(),
            None => {
                // Find and update possible operations
                let ops = {
                    let mut vec = Vec::with_capacity(4);
                    let (x, y) = search_path.location;
                    // up
                    for y in (0..y).rev() {
                        if grid[y as usize][x as usize] {
                            vec.push((x, y));
                        }
                    }
                    // down
                    for y in (y + 1)..y_len {
                        if grid[y as usize][x as usize] {
                            vec.push((x, y));
                        }
                    }
                    // left
                    for x in (0..x).rev() {
                        if grid[y as usize][x as usize] {
                            vec.push((x, y));
                        }
                    }
                    // right
                    for x in (x + 1)..x_len {
                        if grid[y as usize][x as usize] {
                            vec.push((x, y));
                        }
                    }
                    vec
                };
                options.insert(search_path.location, ops.clone());
                ops
            }
        };
        for el in next {
            if el == end {
                return Some(search_path.value + 1);
            }
            if el != search_path.location && !visited.contains(&el) {
                search_queue.push_back(Node {
                    location: el,
                    value: search_path.value + 1,
                });
                visited.insert(el);
            }
        }
    }
    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 as usize]; n as usize];
    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 as usize][x] = chr == '.';
        }
    }

    let mut options: HashMap<(u32, u32), Vec<(u32, u32)>> = 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), &grid, &mut options) {
            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: 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: TIME LIMIT EXCEEDED

Test 26

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 27

Group: 5

Verdict: ACCEPTED