Hypyt

use std::cmp::min;
use std::collections::{HashMap, 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,
    start_cache: &mut HashMap<Coords, Vec<Vec<u64>>>,
    end_cache: &mut HashMap<Coords, Vec<Vec<u64>>>,
) -> Option<u64> {
    if start == end {
        return Some(0);
    }

    let mut search_queue: VecDeque<Node> = VecDeque::new();
    let mut had_start = true;
    let dist_begin = match start_cache.get_mut(&start) {
        Some(s) => s,
        None => {
            start_cache.insert(start, vec![vec![u64::MAX; x_len]; y_len]);
            had_start = false;
            start_cache.get_mut(&start).unwrap()
        }
    };
    if !had_start {
        search_queue.push_back(Node {
            location: start,
            depth: 0,
            from_start: true,
        });
        dist_begin[start.1 as usize][start.0 as usize] = 0;
    }

    let mut had_end = true;
    let dist_end = match end_cache.get_mut(&end) {
        Some(s) => s,
        None => {
            end_cache.insert(end, vec![vec![u64::MAX; x_len]; y_len]);
            had_end = false;
            end_cache.get_mut(&end).unwrap()
        }
    };
    if !had_end {
        search_queue.push_back(Node {
            location: end,
            depth: 0,
            from_start: false,
        });
        dist_end[end.1 as usize][end.0 as usize] = 0;
    }

    if had_start && had_end {
        let mut sums: Vec<u64> = Vec::new();
        for (y, row) in dist_begin.iter().enumerate() {
            for (x, val) in row.iter().enumerate() {
                if *val != u64::MAX && dist_end[y][x] != u64::MAX {
                    sums.push(val + dist_end[y][x]);
                }
            }
        }
        if sums.len() == 0 {
            return None;
        }
        return Some(*sums.iter().min().expect("expected a minimum sum"));
    }

    let mut return_value = None;
    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 {
                        let candidate = value + dist_end[el.1 as usize][el.0 as usize];
                        if return_value.is_none() {
                            return_value = Some(candidate);
                        } else {
                            return_value = Some(min(return_value.unwrap(), candidate))
                        }
                    }
                    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 {
                        let candidate = value + dist_begin[el.1 as usize][el.0 as usize];
                        if return_value.is_none() {
                            return_value = Some(candidate);
                        } else {
                            return_value = Some(min(return_value.unwrap(), candidate))
                        }
                    }
                    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;
                    }
                }
            }
        }
    }
    return_value
}

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();
    let mut start_end_cache: HashMap<(Coords, Coords), Option<u64>> = HashMap::new();
    let mut start_cache: HashMap<Coords, Vec<Vec<u64>>> = HashMap::new();
    let mut end_cache: HashMap<Coords, Vec<Vec<u64>>> = HashMap::new();
    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 start = (x1, y1);
        let end = (x2, y2);
        let res = match start_end_cache.get(&(start, end)) {
            Some(s) => *s,
            None => {
                let p = path_find(
                    start,
                    end,
                    &options_per_row,
                    &options_per_col,
                    m as usize,
                    n as usize,
                    &mut start_cache,
                    &mut end_cache,
                );
                start_end_cache.insert((start, end), p);
                p
            }
        };
        let _ = match res {
            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: TIME LIMIT EXCEEDED

Test 7

Group: 2, 5

Verdict: TIME LIMIT EXCEEDED

Test 8

Group: 2, 5

Verdict: TIME LIMIT EXCEEDED

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: ACCEPTED

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

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