Hypyt

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

fn id(c: (u8, u8), width: u8) -> usize {
    c.0 as usize + width as usize * c.1 as usize
}

fn path_find(
    start: (u8, u8),
    end: (u8, u8),
    grid: &mut Vec<bool>,
    y_len: u8,
    x_len: u8,
) -> Option<u64> {
    if start == end {
        return Some(0);
    }

    let mut search_queue: VecDeque<((u8, u8), u64)> = VecDeque::from([(start, 1)]);
    grid[id(start, x_len)] = true;

    while let Some((coords, depth)) = search_queue.pop_front() {
        if coords == end {
            return Some(depth - 1);
        }
        for y in 0..y_len {
            let id = id((coords.0, y), x_len);
            if !grid[id] {
                grid[id] = true;
                search_queue.push_back(((coords.0, y as u8), depth + 1));
            }
        }
        for x in 0..x_len {
            let id = id((x, coords.1), x_len);
            if !grid[id] {
                grid[id] = true;
                search_queue.push_back(((x as u8, coords.1), depth + 1));
            }
        }
    }
    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<bool> = vec![false; (m as u16 * n as u16) 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[id((x as u8, y), m)] = chr == '*';
        }
    }

    let mut _cache: HashMap<u32, u64> = HashMap::new();
    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), &mut grid.clone(), n, m) {
            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: 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