Hypyt

warning: type `u256` should have an upper camel case name
  --> input/code.rs:20:8
   |
20 | struct u256 {
   |        ^^^^ help: convert the identifier to upper camel case (notice the capitalization): `U256`
   |
   = note: `#[warn(non_camel_case_types)]` on by default

warning: unused variable: `found_target`
   --> input/code.rs:173:13
    |
173 |     let mut found_target = false;
    |             ^^^^^^^^^^^^ help: if this is intentional, prefix it with an underscore: `_found_target`
    |
    = note: `#[warn(unused_variables)]` on by default

warning: variable does not need to be mutable
   --> input/code.rs:173:9
    |
173 |     let mut found_target = false;
    |         ----^^^^^^^^^^^^
    |         |
    |         help: remove this `mut`
    |
    = note: `#[warn(unused_mut)]` on by default

warning: 3 warnings emitted

//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>>,
}

struct u256 {
    data: [u64; 4],
}

impl u256 {
    fn new() -> Self {
        Self { data: [0; 4] }
    }

    fn set(&mut self, bit: usize) { // set to one
        let (block, index) = (bit / 64, bit % 64);
        self.data[block] |= 1 << index;
    }

    fn is_one(&mut self, bit: usize) -> bool {
        let (block, index) = (bit / 64, bit % 64);
        (self.data[block] & (1 << index)) != 0
    }

    fn combine(&mut self, other: &Self) {
        for block in 0..4 {
            self.data[block] = self.data[block] | other.data[block];
        }
    }
}

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() {
        answer_map[r1] = bfs(r1, &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 {
            let mut n1 = (y1 - 1, x1 - 1);
            let mut n2 = (y2 - 1, x2 - 1);


            let mut start_end_pairs = &answer_map[n1.0][n2.0].1;
            if start_end_pairs.is_empty() {
                n1 = (y2 - 1, x2 - 1);
                n2 = (y1 - 1, x1 - 1);
                start_end_pairs = &answer_map[n1.0][n2.0].1;
            }

            let depth = answer_map[n1.0][n2.0].0;
            if !start_end_pairs.is_empty() {
                let mut leaps = INF;
                for pair in start_end_pairs {
                    let start_column = pair.0.contains(&(n1.1));
                    let end_column = pair.1.contains(&(n2.1));
                    if (start_column && end_column) && depth == 1 {
                        if n1.1 == n2.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, graph: &Vec<Node>) -> Vec<(usize, Vec<(&BTreeSet<usize>, &BTreeSet<usize>)>)> {
    let mut start_end_pairs: Vec<(usize, Vec<(&BTreeSet<usize>, &BTreeSet<usize>)>)> = vec![(INF, Vec::new()); graph.len()];
    let mut depth = 0;

    // Then use BFS:
    let mut queue: VecDeque<(usize, usize)> = VecDeque::with_capacity(graph.len());
    let mut explored_nodes: u256 = u256::new();

    let mut found_target = false;

    explored_nodes.set(root_node);
    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!("# - - - - - #");
          println!("{:?}", explored_nodes);*/
        let mut temp_explored_nodes: u256 = u256::new();
        while level_size > 0 {
            /*println!("{}", level_size);*/
            // 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 !explored_nodes.is_one(index) {
                        /*   println!("THIS IS TARGET:");
                             println!("Adjacent node: {:?}", adj_node);*/


                        let end_columns = adj_node;
                        /* println!("END_COLUMNS: {:?} ", adj_node.1);
                           println!("END_COLUMN: {}", end_column);*/ 
                        start_end_pairs[index].0 = depth;
                        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[index].1.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[index].1.push((start_columns, end_columns));
                        }

                        //println!("Adjacent node: {:?}", adj_node);
                        if current.0 == root_node {
                            queue.push_front((index, index));
                        } else {
                            queue.push_back((index, current.1)); // kinda needed for
                                                                 // levels
                        }
                        temp_explored_nodes.set(index);
                    }
                }
            }
            level_size -= 1;
        }
        explored_nodes.combine(&temp_explored_nodes);
    }
    return 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: ACCEPTED

Test 20

Group: 5

Verdict: TIME LIMIT EXCEEDED

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