Hypyt

warning: variable does not need to be mutable
   --> input/code.rs:132:17
    |
132 |             let mut length: usize = if n1.row_index == n2 {0} else {1};
    |                 ----^^^^^^
    |                 |
    |                 help: remove this `mut`
    |
    = note: `#[warn(unused_mut)]` on by default

warning: methods `get_value` and `contains_index` are never used
  --> input/code.rs:49:8
   |
24 | impl BiMap {
   | ---------- methods in this implementation
...
49 |     fn get_value(&self, input: usize) -> usize { // Gives value from index.
   |        ^^^^^^^^^
...
61 |     fn contains_index(&self, input: usize) -> bool {
   |        ^^^^^^^^^^^^^^
   |
   = note: `#[warn(dead_code)]` on by default

warning: function `print_map` is never used
   --> input/code.rs:213:4
    |
213 | fn print_map(map: &Vec<Vec<(usize, BiMap, BiMap)>>) {
    |    ^^^^^^^^^

warning: 3 warnings emitted

use std::collections::HashMap;
use std::io;
 
#[derive(Clone, PartialEq, Debug)]
enum Tile {
    SAFE,
    MONSTER,
}
 
// max size: 250*250
#[derive(Clone, Debug)]
struct Node {
    row_index: usize,
    // row -> columns
    edges: HashMap<usize, Vec<usize>>,
}

#[derive(Clone, Debug)]
struct BiMap {
    vec: Vec<usize>, // index to element
    map: HashMap<usize, usize>, // element to index
}

impl BiMap {
    fn new() -> Self {
        BiMap {
            vec: Vec::new(),
            map: HashMap::new(),
        }
    }

    fn insert(&mut self, input: usize) {
        self.vec.push(input);
        self.map.insert(input, self.vec.len() - 1);
    }

    fn extend(&mut self, input: BiMap) { // Duplicates -> deleted
        for i in input.vec {
            if !self.vec.contains(&i) {
                self.vec.push(i);
            }
        }

        // Deletes duplicates automatically.
        self.map.extend(input.map);

    }

    fn get_value(&self, input: usize) -> usize { // Gives value from index.
        return self.vec[input];
    }

    fn get_index(&self, input: usize) -> usize { // Gives index from value.
        return self.map[&input];
    }

    fn contains_value(&self, input: usize) -> bool {
        return self.vec.contains(&input);
    }

    fn contains_index(&self, input: usize) -> bool {
        return self.map.contains_key(&input);
    }
}
 
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 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");
        for (i, c) in line.chars().enumerate() {
            if c == '.' {
                map[h][i] = Tile::SAFE;
            }
        }
    }

    let mut graph: Vec<Node> = Vec::new();
    // Instantiate graph with nodes. O(n)
    for r in 0..height {
        if !map[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 !map[r1].is_empty() {
            for r2 in 0..height {
                if !map[r2].is_empty() {
                    for i in 0..width {
                        if map[r1][i] == Tile::SAFE {
                            if map[r1][i] == map[r2][i] {
                                if graph[r1].edges.contains_key(&r2) {
                                    //graph[r1].edges[&r2].push(i);
                                    //graph[r1].edges.entry(&r2).or_insert(i);
                                    if let Some(val) = graph[r1].edges.get_mut(&r2) { val.push(i); };
                                } else {
                                    graph[r1].edges.insert(r2, vec![i]);
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    //println!("{:?}", graph);

    const INF: usize = 10_usize.pow(5);
    // row_1, row_2 -> shortest_path_length, starting_cols, ending_cols
    let mut answer_map: Vec<Vec<(usize, BiMap, BiMap)>> = vec![vec![(INF, BiMap::new(), BiMap::new()); height]; height];

    // Creating starting matrix for answer_map. O(n^3). [Get length + all edges]
    for n1 in graph.clone() {
        for (n2, columns) in n1.edges {
            let mut length: usize = if n1.row_index == n2 {0} else {1};
            let mut bi: BiMap = BiMap::new();
            for column in columns {
                bi.insert(column);
            }
            answer_map[n1.row_index][n2] = (length, bi.clone(), bi.clone());
        }
    }

    //print_map(&answer_map);

    // Update matrix to final form. O(n^3) ACtually O(n^4)
    let graph_size: usize = graph.len();
    for ni in 0..graph_size {
        for n1 in 0..graph_size {
            for n2 in 0..graph_size {
                // Make sure all the nodes connect:
                /*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;
                    // Remove all other paths as this one is best / same if from other node.
                    let clone1 = answer_map[n1][ni].1.clone();
                    let clone2 = answer_map[ni][n2].2.clone();
                    if answer_map[n1][n2].0 > sum {
                        answer_map[n1][n2].0 = sum;
                        answer_map[n1][ni].1 = clone1;
                        answer_map[ni][n2].2 = clone2;
                    } else if answer_map[n1][n2].0 == sum { // Otherwise add to list for +1, +1 handling.
                        answer_map[n1][ni].1.extend(clone1);
                        answer_map[ni][n2].2.extend(clone2);
                    }
                //}
            }
        }
    }
    //print_map(&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 = if ans.0 != INF { 2 * ans.0 - 1 } else { INF };
            //println!("leaps beginning: {}", leaps);
            if leaps == INF {
                println!("{}", -1);
            } else {
                //println!("{:?}", ans.1);
                if !ans.1.contains_value(x1 - 1) && !ans.2.contains_value(x2 - 1) {
                    leaps += 2;
                }
                else if ans.1.contains_value(x1 - 1) && !ans.2.contains_value(x2 - 1) {
                    leaps += 1;
                }
                else if !ans.1.contains_value(x1 - 1) && ans.2.contains_value(x2 - 1) {
                    leaps += 1;
                } else if  ans.1.get_index(x1 - 1) != ans.2.get_index(x2 - 1) {
                    leaps += 1;
                }
                
                println!("{}", leaps);
            }
        }
    }
}

fn print_map(map: &Vec<Vec<(usize, BiMap, BiMap)>>) {
    println!("Map for length of shortest path from row to row:");
    let size = map.len();
    for i in 0..size {
        let mut line = String::new();
        for j in 0..size {
            line.push_str(map[i][j].0.to_string().as_str());
            line.push_str(" ");
        }
        println!("{}", line);
    }
    println!("Map for how many columns from starting row to end row:");
    for i in 0..size {
        let mut line = String::new();
        for j in 0..size {
            let size2 = map[i][j].1.vec.len();
            line.push_str("( ");
            for c in 0..size2 {
                line.push_str(map[i][j].1.vec[c].to_string().as_str());
                line.push_str(" ");
            }
            line.push_str(" )");
        }
        println!("{}", line);
    }

    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].2.vec.len();
            line.push_str("( ");
            for c in 0..size2 {
                line.push_str(map[i][j].2.vec[c].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: WRONG ANSWER

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

Test 10

Group: 3, 4, 5

Verdict: ACCEPTED

Test 11

Group: 3, 4, 5

Verdict: WRONG ANSWER

Test 12

Group: 4, 5

Verdict: ACCEPTED

Test 13

Group: 4, 5

Verdict: ACCEPTED

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

Test 25

Group: 5

Verdict: ACCEPTED

Test 26

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 27

Group: 5

Verdict: ACCEPTED