Hypyt

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

warning: type `u256` should have an upper camel case name
 --> input/code.rs:8:8
  |
8 | 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: `width`
  --> input/code.rs:68:18
   |
68 |     let (height, width, query_count): (usize, usize, i32) = (
   |                  ^^^^^ help: if this is intentional, prefix it with an underscore: `_width`
   |
   = note: `#[warn(unused_variables)]` on by default

warning: function `print_map` is never used
   --> input/code.rs:246:4
    |
246 | fn print_map(map: &Vec<Node>) {
    |    ^^^^^^^^^
    |
    = note: `#[warn(dead_code)]` on by default

warning: 4 warnings emitted

//use std::collections::HashSet;
use std::collections::VecDeque;
use std::collections::BTreeSet;
use std::cmp::min;
use std::io;

#[derive(Clone, Debug)]
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(&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];
        }
    }

    fn is_empty(&self) -> bool {
        let mut is_empty = true;
        for block in 0..4 {
            is_empty = self.data[block] == 0;
            if !is_empty {
                return is_empty;
            }
        }
        is_empty
    }
}


fn get_combined(first: &u256, second: &u256) -> u256 { // AND OPERATOR, NOT OR!!!!
    let mut new = u256::new();
    for block in 0..4 {
        new.data[block] = first.data[block] & second.data[block];
    }
    new
}

struct Node {
    //_id: usize,
    // usize on id of node(row) ja hashset on sarakkeet.
    // index on row ja bitset on columnit
    edges: Vec<u256>,
}

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<u256> = vec![u256::new(); height];
    for h in 0..height {
        let mut line = String::new();
        io::stdin().read_line(&mut line).expect("failed");
        graph.push(Node {
            edges: vec![u256::new(); height],
        });
        for (i, c) in line.chars().enumerate() {
            if c == '.' {
                map[h].set(i);
            }
        }
    }

    // Create graph from overlapping indexes.
    for r1 in 0..height {
        for r2 in 0..height { // turn this into r1+1..height for optimization if needed
            if r1 != r2 {
                graph[r1].edges[r2] = get_combined(&map[r1], &map[r2]);
                graph[r2].edges[r1] = get_combined(&map[r1], &map[r2]);
            }
        }
    }


   // print_map(&graph);

    let mut answer_map: Vec<Vec<(usize, Vec<(&u256, &u256)>)>>  = vec![vec![(INF, Vec::new()); height]; height];
    for r1 in 0..graph.len() {
        answer_map[r1] = bfs(r1, &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.is_one(n1.1);
                    let end_column = pair.1.is_one(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<(&u256, &u256)>)> {
    let mut start_end_pairs: Vec<(usize, Vec<(&u256, &u256)>)> = vec![(INF, Vec::new()); graph.len()];
    let mut depth = 0;

    // Then use BFS:
    // (node index, from which node it began(the one root_node branched into))
    let mut queue: VecDeque<(usize, usize)> = VecDeque::with_capacity(graph.len());
    let mut explored_nodes: u256 = u256::new();

    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!("VISITED: {:?}", explored_nodes.to_string());
        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();
            // Index is to which row and edge is which columns
            for (index, edge) in graph[current.0].edges.iter().enumerate() {
                // Is actually adjacent:
                //println!("Edgedata: {:?} is_empty?: {}", edge.data, edge.data.is_empty());
                if !edge.is_empty() {
                    if !explored_nodes.is_one(index) {
                        /*   println!("THIS IS TARGET:");
                             println!("Adjacent node: {:?}", edge);*/


                        let end_columns = edge;
                        /* println!("END_COLUMNS: {:?} ", edge.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[*edge.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: {:?}", edge);
                        if !explored_nodes.is_one(index) && !temp_explored_nodes.is_one(index) {
                            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: 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: ACCEPTED

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

Test 27

Group: 5

Verdict: ACCEPTED