Hypyt

//use std::collections::HashSet;
use std::collections::VecDeque;
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<Vec<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(),
    );

    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![Vec::new(); height],
        });
        for (i, c) in line.chars().enumerate() {
            if c == '.' {
                map[h][i] = Tile::SAFE;
            }
        }
    }

    //const INF: usize = 10_usize.pow(5);
    // 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 = vec![i];
                            graph[r1].edges[r2] = set;
                        } else {
                            graph[r1].edges[r2].push(i);
                           /* if let Some(val) = graph[r1].edges.get_mut(&r2) {
                                val.insert(i);
                            };*/
                        }
                    }
                }
            }
        }
    }

    //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.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 mut depth = 0;
            let mut leaps = 2000;

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

            let root_node = y1 - 1;
            let target_node = y2 - 1;

            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();
                    let mut index = 0;
                    for adj_node in &graph[current.0].edges {
                        // 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_column = adj_node.contains(&(x2 - 1));
                                /* println!("END_COLUMNS: {:?} ", adj_node.1);
                                   println!("END_COLUMN: {}", end_column);*/
                                if depth == 1 {
                                    let start_column = graph[index].edges[current.0].contains(&(x1 - 1));
                                    /* println!("START_COLUMNS: {:?} ", graph[*adj_node.0].edges[&current.0]);
                                       println!("START_COLUMN: {}", start_column);*/
                                    if start_column && end_column { // handle specific edgecase
                                        if x2 - 1 == x1 - 1 {
                                            leaps = 0;
                                        } else {
                                            leaps = 1;
                                        }
                                    } else {
                                        set_leaps(start_column, end_column, &mut leaps);
                                    }
                                } else {
                                    let start_column = graph[current.1].edges[root_node].contains(&(x1 - 1));
                                    /*println!("START_COLUMNS: {:?} ", current.1);
                                      println!("START_COLUMN: {}", start_column);*/
                                    set_leaps(start_column, end_column, &mut leaps);
                                }
                            } 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
                                }
                            }
                        }
                        index += 1;
                    }
                    level_size -= 1;
                }
                if found_target {
                    /*  println!("FOUND TARGET! LEAPS: {:?}", leaps);
                        println!("queue after: {:?}", queue);*/
                    break;
                }
            }

            if !found_target {
                println!("{}", -1);
            } else {
                if leaps == 2000 { //emt miks tää mut trust
                    leaps = 0;
                }
                println!("{}", leaps + 2 * depth - 1);
            }
        }
    }
}

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

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

Test 16

Group: 5

Verdict: ACCEPTED

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

Test 25

Group: 5

Verdict: ACCEPTED

Test 26

Group: 5

Verdict: ACCEPTED

Test 27

Group: 5

Verdict: ACCEPTED