Hypyt

use std::io;
use std::collections::HashMap;
use std::cmp::min;

fn main() {
    let mut input = String::new();
    io::stdin().read_line(&mut input).expect("failed to readline");
    let mut iter = input.trim().split_whitespace();
    let (height, _width, query_count): (usize, usize, i32) = (
        iter.next().unwrap().parse().unwrap(),
        iter.next().unwrap().parse().unwrap(),
        iter.next().unwrap().parse().unwrap(),
    );
    // most fresh (height, start_i, end_i) and tiles related to it.
    //let mut areas: HashMap<(usize, usize, usize), Vec<(usize, usize)>> = HashMap::new();//::with_capacity(height as usize);
    let mut tiles: Vec<(usize, usize)> = Vec::new();
    for h in 0..height {
        let mut line = String::new();
        io::stdin().read_line(&mut line).expect("failed");
        /*let mut indexed_tiles: Vec<(usize, usize)> = Vec::new();
        let mut indexing: bool = false;
        let mut i_start: usize = 0;*/
        for (i, c) in line.chars().enumerate() {
            if c == '.' {
                tiles.push((i, h));   
            }
        }
        /*    if c == '.' {
                if !indexing {
                    indexing = true;
                    i_start = i;
                }
                indexed_tiles.push((i, h));
            } else if (c == '*' || i == width - 1) && indexing {
                indexing = false;
                let mut overlapping_areas: HashMap<(usize, usize, usize), Vec<(usize, usize)>> = HashMap::new();
                for (key, value) in &areas {
                    if key.0 + 1 == h && (key.2 >= i_start && i - 1 >= key.1) {
                        //println!("Overlapping!! {:?} with {:?}", value, indexed_tiles);
                        overlapping_areas.insert(*key, value.to_vec());
                    }
                }
                if !overlapping_areas.is_empty() {
                    for (key, value) in &overlapping_areas {
                        indexed_tiles.extend(value);
                        areas.remove(key);
                    }
                }
                //println!("TEST: {:?}", indexed_tiles);
                areas.insert((h, i_start, i - 1), indexed_tiles);
                indexed_tiles = Vec::new();
            }
        }*/
    }
    //println!("{:?}", areas);
    let mut calculated_values: HashMap<(usize, usize), HashMap<(usize, usize), i32>> = HashMap::new();

    const INF: i32 = 10_i32.pow(5);
    // Create starting matrix:
    /*for (_, value) in &areas {
        for tile_1 in value {
            if !calculated_values.contains_key(tile_1) {
                calculated_values.insert(*tile_1, HashMap::new());
            }
            for tile_2 in value {
                if tile_1 == tile_2  {
                    if let Some(val) = calculated_values.get_mut(&tile_1) { val.insert(*tile_2, 0); }
                } else if is_next_to(*tile_1, *tile_2) {
                    if let Some(val) = calculated_values.get_mut(&tile_1) { val.insert(*tile_2, 1); }
                } else {
                    if let Some(val) = calculated_values.get_mut(&tile_1) { val.insert(*tile_2, INF); }
                }
            }
        }
    }*/
    // Create starting matrix:
    for tile_1 in &tiles {
        if !calculated_values.contains_key(&tile_1) {
            calculated_values.insert(*tile_1, HashMap::new());
        }
        for tile_2 in &tiles {
            if tile_1 == tile_2  {
                if let Some(val) = calculated_values.get_mut(&tile_1) { val.insert(*tile_2, 0); }
            } else if is_next_to(*tile_1, *tile_2) {
                if let Some(val) = calculated_values.get_mut(&tile_1) { val.insert(*tile_2, 1); }
            } else {
                if let Some(val) = calculated_values.get_mut(&tile_1) { val.insert(*tile_2, INF); }
            }
        }
    }

    // Solve all INF cases.
    for i_tile in &tiles {
        for tile_1 in &tiles {
            for tile_2 in &tiles {
                if calculated_values[&tile_1][&i_tile] != INF && calculated_values[&i_tile][&tile_2] != INF {
                    let option_1 = calculated_values[&tile_1][&tile_2];
                    let option_2 = calculated_values[&tile_1][&i_tile] + calculated_values[&i_tile][&tile_2];
                    if let Some(val) = calculated_values.get_mut(&tile_1) {
                        val.insert(*tile_2, min(option_1, option_2));
                    }
                }
            }
        }
    }

    //println!("{:?}", calculated_values);
    for _ in 0..query_count {
        let mut query = String::new();
        io::stdin().read_line(&mut query).expect("failed to readline");
        let mut iter = query.trim().split_whitespace();
        let (y1, x1, y2, x2): (usize, usize, usize, usize) = (
            iter.next().unwrap().parse().unwrap(),
            iter.next().unwrap().parse().unwrap(),
            iter.next().unwrap().parse().unwrap(),
            iter.next().unwrap().parse().unwrap(),
        );
        let p1 = (x1 - 1, y1 - 1);
        let p2 = (x2 - 1, y2 - 1);
        let calced = calculated_values[&p1][&p2];
        if calced == INF {
            println!("{}", -1);
        } else {
            println!("{}", calculated_values[&p1][&p2]);
        }
    }
}

fn is_next_to(tile_a: (usize, usize), tile_b: (usize, usize)) -> bool {
    if tile_a.0 == tile_b.0 || tile_a.1 == tile_b.1 {
        return true;
    }
    return false;
}

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