Hypyt

use std::collections::HashMap;
use std::io;

#[derive(Clone, PartialEq)]
enum Tile {
    SAFE,
    MONSTER,
}

// max size: 250*250
#[derive(Clone, Debug)]
struct Node {
    row_index: usize,
    // row, col
    //edges: Vec<(usize, usize)>,
    edges: HashMap<usize, usize>,
}

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(),
    );

    // Get all indexes for each row. O(n^2)
    let mut indexes_per_row: Vec<Vec<Tile>> = vec![vec![Tile::MONSTER; width]; height];
    for h in 0..height {
        let mut line = String::new();
        io::stdin().read_line(&mut line).expect("failed");
        for (i, c) in line.chars().enumerate() {
            if c == '.' {
                indexes_per_row[h][i] = Tile::SAFE;
            }
        }
    }

    let mut graph: Vec<Node> = Vec::new();
    // Instantiate graph with nodes. O(n)
    for r in 0..height {
        if !indexes_per_row[r].is_empty() {
            graph.push(Node {
                row_index: r,
                edges: HashMap::new(),
            });
        }
    }

    // Create graph from overlapping indexes. O(n^3)
    for r1 in 0..height {
        if !indexes_per_row[r1].is_empty() {
            for r2 in 0..height {
                if !indexes_per_row[r2].is_empty() {
                    //&& r1 != r2 {
                    for i in 0..width {
                        if indexes_per_row[r1][i] == Tile::SAFE {
                            if indexes_per_row[r1][i] == indexes_per_row[r2][i] {
                                graph[r1].edges.insert(r2, i);
                            }
                        }
                    }
                }
            }
        }
    }
    //println!("{:?}", graph);

    // i: Row_1, j: Row_2 -> length, (shortest path starting column and ending column)
    const INF: usize = 10_usize.pow(5);
    // inside vecvec -> (length, start_cols, end_cols, pairs) MAX RAM = 156,5mb or something < 250mb
    let mut answer_map: Vec<Vec<(usize, Vec<usize>, Vec<usize>, Vec<(usize, usize)>)>> =
        vec![vec![(INF, Vec::new(), Vec::new(), Vec::new()); graph.len()]; graph.len()];

    // Creating starting matrix for answer_map. O(n^2). [Get length + all edges]
    // For example: NODE1 ->(c_1 and c_2) NODE2 = 1, (c_1, c_1) && 1, (c_2, c_2)
    for n1 in graph.clone() {
        // WARN: Clone here might have adverse effects to speed?
        for n2 in n1.edges {
            let mut length: usize = 1;
            if n1.row_index == n2.0 {
                length = 0;
            }
            // NOTE: Might have issues, since if same row then columns are set, but probably not since initial processing of
            // the queries should remove such issues.
            answer_map[n1.row_index][n2.0] = (length, vec![n2.1], vec![n2.1], vec![(n2.1, n2.1)]);
        }
    }

    // Update matrix to final form. O(n^3)
    let graph_size: usize = graph.len();
    for ni in 0..graph_size {
        for n1 in 0..graph_size {
            for n2 in 0..graph_size {
                if graph[n1].edges.contains_key(&n2)
                    && graph[n1].edges.contains_key(&ni)
                    && graph[ni].edges.contains_key(&n2)
                {
                    let sum = answer_map[n1][ni].0 + answer_map[ni][n2].0;
                    if answer_map[n1][n2].0 > sum {
                        answer_map[n1][n2].0 = sum;
                        answer_map[n1][n2].1 = vec![graph[n1].edges[&ni]];
                        answer_map[n1][n2].2 = vec![graph[ni].edges[&n2]];
                        answer_map[n1][n2].3 = vec![(graph[n1].edges[&ni], graph[ni].edges[&n2])];
                    } else {
                        answer_map[n1][n2].1.push(graph[n1].edges[&ni]);
                        answer_map[n1][n2].2.push(graph[ni].edges[&n2]);
                        answer_map[n1][n2]
                            .3
                            .push((graph[n1].edges[&ni], graph[ni].edges[&n2]));
                    }
                }
            }
        }
    }

    //println!("{:?}", answer_map);
    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(),
        );
        if x1 == x2 && y1 == y2 {
            println!("{}", 0);
        } else if x1 == x2 || y1 == y2 {
            println!("{}", 1);
        } else {
            let ans = &answer_map[y1 - 1][y2 - 1];
            let mut leaps = ans.0;
            if leaps == INF {
                println!("{}", -1);
            } else {
                if !ans.1.contains(&(y1 - 1)) {
                    leaps += 1;
                    if !ans.2.contains(&(y2 - 1)) {
                        leaps += 1;
                    }
                } else {
                    if !ans.2.contains(&(y2 - 1)) {
                        leaps += 1;
                    } else if !ans.3.contains(&(y1 - 1, y2 - 1)) {
                        leaps += 1;
                    }
                }
                println!("{}", leaps);
            }
        }
    }
}

Test 1 (public)

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

Test 2

Group: 1, 2, 3, 4, 5

Verdict: WRONG ANSWER

Test 3

Group: 1, 2, 3, 4, 5

Verdict: WRONG ANSWER

Test 4

Group: 1, 2, 3, 4, 5

Verdict: WRONG ANSWER

Test 5

Group: 1, 2, 3, 4, 5

Verdict: WRONG ANSWER

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: WRONG ANSWER

Test 10

Group: 3, 4, 5

Verdict: WRONG ANSWER

Test 11

Group: 3, 4, 5

Verdict: WRONG ANSWER

Test 12

Group: 4, 5

Verdict: WRONG ANSWER

Test 13

Group: 4, 5

Verdict: WRONG ANSWER

Test 14

Group: 4, 5

Verdict: WRONG ANSWER

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: WRONG ANSWER

Test 20

Group: 5

Verdict: WRONG ANSWER

Test 21

Group: 5

Verdict: WRONG ANSWER

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