Hypyt

warning: unused import: `std::collections::HashMap`
 --> input/code.rs:2:5
  |
2 | use std::collections::HashMap;
  |     ^^^^^^^^^^^^^^^^^^^^^^^^^
  |
  = note: `#[warn(unused_imports)]` on by default

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

warning: variable does not need to be mutable
   --> input/code.rs:127:21
    |
127 |                 let mut second_correct = ans.2.contains(&(x2 - 1));
    |                     ----^^^^^^^^^^^^^^
    |                     |
    |                     help: remove this `mut`

warning: 3 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, HashSet<usize>, HashSet<usize>, HashSet<(usize, usize)>)>> = vec![vec![(INF, HashSet::new(), HashSet::new(), HashSet::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].0 == INF {
                            let length = if r1 == r2 {0} else {1};
                            answer_map[r1][r2].0 = length;
                            answer_map[r1][r2].1.insert(i);
                            answer_map[r1][r2].2.insert(i);
                            answer_map[r1][r2].3.insert((i, i));
                        } else {
                            answer_map[r1][r2].1.insert(i);
                            answer_map[r1][r2].2.insert(i);
                            answer_map[r1][r2].3.insert((i, i));
                        }
                    }
                }
            }
        }
    }

    //print_map(&answer_map);

    // 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 no overlapping nodes:
                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 {
                        let clone1 = answer_map[n1][ni].1.clone();
                        let clone2 = answer_map[ni][n2].2.clone();
                        answer_map[n1][n2].3 = HashSet::new();
                        for start_col in &clone1 {
                            for end_col in &clone2 {
                                answer_map[n1][n2].3.insert((*start_col, *end_col));
                            }
                        }
                        answer_map[n1][n2].0 = sum;
                        answer_map[n1][n2].1 = clone1;
                        answer_map[n1][n2].2 = clone2;
                    } else if answer_map[n1][n2].0 == sum {
                        let clone1 = answer_map[n1][ni].1.clone();
                        let clone2 = answer_map[ni][n2].2.clone();
                        for start_col in &clone1 {
                            answer_map[n1][n2].1.insert(*start_col);
                            for end_col in &clone2 {
                                if !answer_map[n1][n2].2.contains(end_col) {
                                    answer_map[n1][n2].2.insert(*end_col);
                                }
                                answer_map[n1][n2].3.insert((*start_col, *end_col));
                            }
                        }
                    }
                }
            }
        }
    }


    //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(&(x1 - 1));
                let mut second_correct = ans.2.contains(&(x2 - 1));

                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.3.contains(&((x1 - 1), (x2 - 1))) {
                    leaps += 1;
                }

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

/*fn print_map(map: &Vec<Vec<(usize, HashMap<usize, HashSet<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("( ");
line.push_str(format!("{:?}", map[i][j].1).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: 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: TIME LIMIT EXCEEDED

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

Test 20

Group: 5

Verdict: ACCEPTED

Test 21

Group: 5

Verdict: ACCEPTED

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