Hypyt

//use std::collections::HashSet;
use std::collections::VecDeque;
use std::collections::BTreeSet;
use std::cmp::min;
use std::io;
 
#[derive(Clone, PartialEq, Debug)]
enum Tile {
    Safe,
    Monster,
}
 
struct Node {
    //_id: usize,
    // usize on id of node(row) ja hashset on sarakkeet.
    edges: Vec<BTreeSet<usize>>,
}
 


const INF: usize = 10_usize.pow(5);
fn main() {
    let mut input = String::new();
    io::stdin()
        .read_line(&mut input)
        .expect("failed to readline");
    let mut iter = input.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(),
    );
 
    let mut graph: Vec<Node> = Vec::new();
    // Get all indexes for each row. O(n^2)
    let mut map: 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");
        graph.push(Node {
           // _id: h,
            edges: vec![BTreeSet::new(); height],
        });
        for (i, c) in line.chars().enumerate() {
            if c == '.' {
                map[h][i] = Tile::Safe;
            }
        }
    }
 
    // Create graph from overlapping indexes. O(n^3)
    for r1 in 0..height {
        for r2 in 0..height {
            if r1 != r2 {
                for i in 0..width {
                    if map[r1][i] == Tile::Safe && map[r1][i] == map[r2][i] {
                        if graph[r1].edges[r2].is_empty() {
                            let set = BTreeSet::from([i]);
                            graph[r1].edges[r2] = set;
                        } else {
                            graph[r1].edges[r2].insert(i);
                        }
                    }
                }
            }
        }
    }



    let mut answer_map: Vec<Vec<(usize, Vec<(&BTreeSet<usize>, &BTreeSet<usize>)>)>>  = vec![vec![(INF, Vec::new()); height]; height];
    for r1 in 0..graph.len() {
        for r2 in 0..graph.len() { // change to r1+1..graph.len() for small optimization? doesnt
                                   // optimize much, so it isn't really that good, but an option.
            answer_map[r1][r2] = bfs(r1, r2, &graph);
        }
    }
 
    //print_map(&graph);
 
    for _ in 0..query_count {
        let mut query = String::new();
        io::stdin()
            .read_line(&mut query)
            .expect("failed to readline");
        let mut iter = query.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 { unsafe {
            let depth = answer_map.get_unchecked(y1 - 1).get_unchecked(y2 - 1).0;
            let start_end_pairs = &answer_map.get_unchecked(y1 - 1).get_unchecked(y2 - 1).1;
            if !start_end_pairs.is_empty() {
                let mut leaps = INF;
                for pair in start_end_pairs {
                    let start_column = pair.0.contains(&(x1 - 1));
                    let end_column = pair.1.contains(&(x2 - 1));
                    if (start_column && end_column) && depth == 1 {
                        if x2 - 1 == x1 - 1 {
                            leaps = 0;
                        } else {
                            leaps = 1;
                        }
                    } else {
                        set_leaps(start_column, end_column, &mut leaps);
                    }
                }
                println!("{}", leaps + 2 * depth - 1);
            } else {
                println!("{}", -1);
            }
        } }
    }
}
#[inline]
fn set_leaps(start_column: bool, end_column: bool, leaps: &mut usize) {
    if (!start_column && end_column) || (start_column && !end_column) {
        *leaps = min(*leaps, 1);
    } else if !start_column && !end_column {
        *leaps = min(*leaps, 2);
    } else {
        *leaps = min(*leaps, 0);
    }
}

fn bfs(root_node: usize, target_node: usize, graph: &Vec<Node>) -> (usize, Vec<(&BTreeSet<usize>, &BTreeSet<usize>)>) {
    let mut start_end_pairs: Vec<(&BTreeSet<usize>, &BTreeSet<usize>)> = Vec::new();
    let mut depth = 0;

    // Then use BFS:
    let mut queue: VecDeque<(usize, usize)> = VecDeque::with_capacity(graph.len());
    let mut explored_nodes: Vec<bool> = vec![false; graph.len()];

    let mut found_target = false;

    explored_nodes[root_node] = true;
    queue.push_front((root_node, 0));

    while !queue.is_empty() {
        depth += 1;
        let mut level_size = queue.len();
        /*println!("# - - - - - #");
          println!("DEPTH: {:?}", depth);
          println!("QUEUE: {:?} WHICH IS LEN: {:?}", queue, level_size);
          println!("# - - - - - #");*/
        while level_size > 0 {
            // current_row, start_row
            let current: (usize, usize) = *queue.front().unwrap();
            // println!("CURRENT: {:?}", current);
            queue.pop_front();
            for (index, adj_node) in graph[current.0].edges.iter().enumerate() {
                // If it is target_node.
                if !adj_node.is_empty() {
                    if index == target_node {
                        /*   println!("THIS IS TARGET:");
                             println!("Adjacent node: {:?}", adj_node);*/
                        found_target = true;


                        let end_columns = adj_node;
                        /* println!("END_COLUMNS: {:?} ", adj_node.1);
                           println!("END_COLUMN: {}", end_column);*/
                        if depth == 1 {
                            let start_columns = &graph[index].edges[current.0];
                            /* println!("START_COLUMNS: {:?} ", graph[*adj_node.0].edges[&current.0]);
                               println!("START_COLUMN: {}", start_column);*/
                            start_end_pairs.push((start_columns, end_columns));
                        } else {
                            let start_columns = &graph[current.1].edges[root_node];
                            /*println!("START_COLUMNS: {:?} ", current.1);
                              println!("START_COLUMN: {}", start_column);*/
                            start_end_pairs.push((start_columns, end_columns));
                        }

                    } else if !explored_nodes[index] && !found_target {
                        //println!("Adjacent node: {:?}", adj_node);
                        explored_nodes[index] = true;
                        if current.0 == root_node {
                            queue.push_front((index, index));
                        } else {
                            queue.push_back((index, current.1)); // kinda needed for
                                                                 // levels
                        }
                    }
                }
            }
            level_size -= 1;
        }
        if found_target {
            /*  println!("FOUND TARGET! LEAPS: {:?}", leaps);
                println!("queue after: {:?}", queue);*/
            break;
        }
    }

    if !found_target {
        return (INF, Vec::new());
    } else {
        return (depth, start_end_pairs);
    }
}

/*fn print_map(map: &Vec<Node>) {
  println!("Node and its edges:");
  let size = map.len();
  for i in 0..size {
  let mut line = String::new();
  line.push_str(format!("{:?}", map[i].edges).as_str());
/*line.push_str("(");
for j in 0..size {
line.push_str(map[i].edges[j]);
line.push_str(" ");
}*/
line.push_str(")");
println!("{}", line);
}
println!("END!");

/*println!("Map for how many columns from starting to end row, but at the end:");
  for i in 0..size {
  let mut line = String::new();
  for j in 0..size {
  let size2 = map[i][j].1.len();
  line.push_str("( ");
  for c in 0..size2 {
  line.push_str(map[i][j].1[c]1.to_string().as_str());
  line.push_str(" ");
  }
  line.push_str(" )");
  }
  println!("{}", line);
  }*/
}*/

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

Test 8

Group: 2, 5

Verdict: ACCEPTED

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: TIME LIMIT EXCEEDED

Test 16

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 17

Group: 5

Verdict: ACCEPTED

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

Test 26

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 27

Group: 5

Verdict: ACCEPTED