Hypyt

use std::io::{
    BufReader,
    BufWriter,
    BufRead,
    Write,
    stdin,
    stdout,
    Stdin,
    StdoutLock
};
use std::collections::{
    HashSet,
    VecDeque
};
 
fn main() {
    let mut reader: BufReader<Stdin> = BufReader::new(stdin());
    let mut writer: BufWriter<StdoutLock<'_>> = BufWriter::new(stdout().lock());
 
    let mut input: String = String::new();
    reader.read_line(&mut input).unwrap();
    let input: Vec<usize> = input.trim().split(" ").map(|s: &str| s.parse::<usize>().unwrap()).collect();
 
    let mut row_cells: Vec<Vec<usize>> = vec![vec![]; input[0]];
    let mut col_cells: Vec<Vec<usize>> = vec![vec![]; input[1]];
    parse_graph(&mut row_cells, &mut col_cells, &input, &mut reader);
 
    let mut queries: HashSet<usize> = HashSet::new();
    let mut queries_order: Vec<(usize, usize)> = Vec::new();
    for _ in 0..input[2] {
        let mut query: String = String::new();
        reader.read_line(&mut query).unwrap();
        let query: Vec<usize> = query.trim().split(" ").map(|s: &str| s.parse::<usize>().unwrap()).collect();
 
        let start: usize = (query[0] - 1) * input[1] + (query[1] - 1);
        let goal: usize = (query[2] - 1) * input[1] + (query[3] - 1);
        if !queries.contains(&start) { queries.insert(start); }
        queries_order.push((start, goal));
    }
 
    let mut distance_table: Vec<Vec<i32>> = vec![vec![-1; input[0] * input[1]]; input[0] * input[1]];
    get_distance_table(&mut distance_table, &queries, &input, &row_cells, &col_cells);

    for (start, goal) in queries_order {
        writeln!(writer, "{}", distance_table[start][goal]).unwrap();
    }
}

fn parse_graph(row_cells: &mut Vec<Vec<usize>>, col_cells: &mut Vec<Vec<usize>>, input: &Vec<usize>, reader: &mut BufReader<Stdin>) {
    for r in 0..input[0] {
        let mut row: String = String::new();
        reader.read_line(&mut row).unwrap();
        for (c, node) in row.chars().enumerate() {
            if node == '.' {
                row_cells[r].push(r * input[1] + c);
                col_cells[c].push(r * input[1] + c);
            }
        }
    }
}

fn get_distance_table(table: &mut Vec<Vec<i32>>, queries: &HashSet<usize>, input: &Vec<usize>, row_cells: &Vec<Vec<usize>>, col_cells: &Vec<Vec<usize>>) {
    for &root in queries {
        bfs(root, &mut table[root], input, row_cells, col_cells);
    }
}

fn bfs(root: usize, dist: &mut Vec<i32>, input: &Vec<usize>, row_cells: &Vec<Vec<usize>>, col_cells: &Vec<Vec<usize>>) {
    let mut visited: Vec<bool> = vec![false; input[0] * input[1]];
    let mut rows_visited: Vec<bool> = vec![false; input[0]];
    let mut cols_visited: Vec<bool> = vec![false; input[1]];
    let mut queue: VecDeque<usize> = VecDeque::from([root]);

    dist[root] = 0;
    visited[root] = true;

    while let Some(current) = queue.pop_front() {
        let current_dist: i32 = dist[current];
        let r: usize = current / input[1];
        let c: usize = current % input[1];

        if !rows_visited[r] {
            rows_visited[r] = true;
            for &neighbour in &row_cells[r] {
                if !visited[neighbour] {
                    dist[neighbour] = current_dist + 1;
                    visited[neighbour] = true;
                    queue.push_back(neighbour);
                }
            }
        }

        if !cols_visited[c] {
            cols_visited[c] = true;
            for &neighbour in &col_cells[c] {
                if !visited[neighbour] {
                    dist[neighbour] = current_dist + 1;
                    visited[neighbour] = true;
                    queue.push_back(neighbour);
                }
            }
        }
    }
}

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

Test 7

Group: 2, 5

Verdict: RUNTIME ERROR

Test 8

Group: 2, 5

Verdict: RUNTIME ERROR

Test 9

Group: 3, 4, 5

Verdict: ACCEPTED

Test 10

Group: 3, 4, 5

Verdict: ACCEPTED

Test 11

Group: 3, 4, 5

Verdict: ACCEPTED

Test 12

Group: 4, 5

Verdict: ACCEPTED

Test 13

Group: 4, 5

Verdict: ACCEPTED

Test 14

Group: 4, 5

Verdict: ACCEPTED

Test 15

Group: 5

Verdict: RUNTIME ERROR

Test 16

Group: 5

Verdict: RUNTIME ERROR

Test 17

Group: 5

Verdict: RUNTIME ERROR

Test 18

Group: 5

Verdict: RUNTIME ERROR

Test 19

Group: 5

Verdict: RUNTIME ERROR

Test 20

Group: 5

Verdict: RUNTIME ERROR

Test 21

Group: 5

Verdict: RUNTIME ERROR

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

Test 27

Group: 5

Verdict: RUNTIME ERROR