Hypyt

warning: unused variable: `key`
   --> input/code.rs:116:22
    |
116 |                 for (key, value) in &ans.1 {
    |                      ^^^ help: if this is intentional, prefix it with an underscore: `_key`
    |
    = note: `#[warn(unused_variables)]` on by default

warning: variable does not need to be mutable
   --> input/code.rs:114:21
    |
114 |                 let mut first_correct = ans.1.contains_key(&(x1 - 1));
    |                     ----^^^^^^^^^^^^^
    |                     |
    |                     help: remove this `mut`
    |
    = note: `#[warn(unused_mut)]` on by default

warning: 2 warnings emitted

use std::io;
use std::collections::HashMap;
use std::collections::HashSet;
 
#[derive(Clone, PartialEq, Debug)]
enum Tile {
    SAFE,
    MONSTER,
}

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;
            }
        }
    }

    const INF: usize = 10_usize.pow(5);
    // row1, row2 -> length and (col to cols) # perhaps turn vec into set
    let mut answer_map: Vec<Vec<(usize, HashMap<usize, HashSet<usize>>)>> = vec![vec![(INF, HashMap::new()); height]; height];
    // Create graph from overlapping indexes. O(n^3)
    for r1 in 0..height {
        for r2 in 0..height {
            for i in 0..width {
                if map[r1][i] == Tile::SAFE {
                    if map[r1][i] == map[r2][i] {
                        if !answer_map[r1][r2].1.contains_key(&i) {
                            let length = if r1 == r2 {0} else {1};
                            let mut set = HashSet::new();
                            set.insert(i);
                            let mut hash = HashMap::new();
                            hash.insert(i, set);
                            answer_map[r1][r2] = (length, hash);
                        } else {
                            let mut set = HashSet::new();
                            set.insert(i);
                            if let Some(val) = answer_map[r1][r2].1.get_mut(&i) { val.insert(i); };
                        }
                    }
                }
            }
        }
    }

    // Update matrix to final form. O(n^3)
    for ni in 0..height {
        for n1 in 0..height {
            for n2 in 0..height {
                // Make sure all the nodes connect:
                if (ni != n1 && ni != n2) && n1 != 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;
                        for (key, _value) in answer_map[n1][n2].1.clone().into_iter() {
                            answer_map[n1][n2].1.insert(key, HashSet::new());
                            for (_key2, value2) in answer_map[ni][n2].1.clone().into_iter() {
                                if let Some(val) = answer_map[n1][n2].1.get_mut(&key) { val.extend(value2) };
                            }
                        }
                    } else if answer_map[n1][n2].0 == sum { // Otherwise add to list for +1, +1 handling.
                        for (_key, value) in answer_map[ni][n2].1.clone().into_iter() {
                            for (key2, _value2) in answer_map[n1][n2].1.clone().into_iter() {
                                if let Some(val) = answer_map[n1][n2].1.get_mut(&key2) { val.extend(value.clone()); };
                            }
                        }
                    }
                }
            }
        }
    }

    //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 {
                let mut first_correct = ans.1.contains_key(&(x1 - 1));
                let mut second_correct = false;
                for (key, value) in &ans.1 {
                    if value.contains(&(x2 - 1)) {
                        second_correct = true;
                        break;
                    }
                }


                if !first_correct && !second_correct {
                    leaps += 2;
                }
                else if first_correct && !second_correct {
                    leaps += 1;
                }
                else if !first_correct && second_correct {
                    leaps += 1;
                } else if ans.1[&(x1 - 1)].contains(&(x2 - 1)) {
                    leaps += 1;
                }

                println!("{}", leaps);
            }
        }
    }
}

/*fn print_map(map: &Vec<Vec<(usize, Vec<(usize, usize)>)>>) {
    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.len();
            line.push_str("( ");
            for c in 0..size2 {
                line.push_str(map[i][j].1[c].0.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].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: 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: ACCEPTED

Test 6

Group: 2, 5

Verdict: TIME LIMIT EXCEEDED

Test 7

Group: 2, 5

Verdict: WRONG ANSWER

Test 8

Group: 2, 5

Verdict: WRONG ANSWER

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

Test 18

Group: 5

Verdict: WRONG ANSWER

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