use std::collections::HashSet;
use std::collections::VecDeque;
use std::cmp::min;
use std::io;
use ahash::AHashSet;
#[derive(Clone, PartialEq, Debug)]
enum Tile {
SAFE,
MONSTER,
}
struct Node {
_id: usize,
// usize on id of node(row) ja hashset on sarakkeet.
edges: Vec<AHashSet<usize>>,
}
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(),
);
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![AHashSet::new(); height],
});
for (i, c) in line.chars().enumerate() {
if c == '.' {
map[h][i] = Tile::SAFE;
}
}
}
//const INF: usize = 10_usize.pow(5);
// 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 mut set = AHashSet::new();
set.insert(i);
graph[r1].edges[r2] = set;
} else {
graph[r1].edges[r2].insert(i);
/* if let Some(val) = graph[r1].edges.get_mut(&r2) {
val.insert(i);
};*/
}
}
}
}
}
}
//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.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 mut depth = 0;
let mut leaps = 2000;
// Then use BFS:
let mut queue: VecDeque<(usize, &AHashSet<usize>)> = VecDeque::new();
let mut explored_nodes: Vec<bool> = vec!(false; height);
let root_node = y1 - 1;
let target_node = y2 - 1;
let mut found_target = false;
explored_nodes[root_node] = true;
let dummy: AHashSet<usize> = AHashSet::new();
queue.push_front((root_node, &dummy));
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!("# - - - - - #");*/
while level_size > 0 {
let current: (usize, &AHashSet<usize>) = *queue.front().unwrap();
// println!("CURRENT: {:?}", current);
queue.pop_front();
let mut index = 0;
for adj_node in &graph[current.0].edges {
// If it is target_node.
if !adj_node.is_empty() {
if index == target_node {
/* println!("THIS IS TARGET:");
println!("Adjacent node: {:?}", adj_node);*/
found_target = true;
let end_column = adj_node.contains(&(x2 - 1));
/* println!("END_COLUMNS: {:?} ", adj_node.1);
println!("END_COLUMN: {}", end_column);*/
if depth == 1 {
let start_column = graph[index].edges[current.0].contains(&(x1 - 1));
/* println!("START_COLUMNS: {:?} ", graph[*adj_node.0].edges[¤t.0]);
println!("START_COLUMN: {}", start_column);*/
if start_column && end_column { // handle specific edgecase
if x2 - 1 == x1 - 1 {
leaps = 0;
} else {
leaps = 1;
}
} else {
set_leaps(start_column, end_column, &mut leaps);
}
} else {
let start_column = current.1.contains(&(x1 - 1));
/*println!("START_COLUMNS: {:?} ", current.1);
println!("START_COLUMN: {}", start_column);*/
set_leaps(start_column, end_column, &mut leaps);
}
} else if !explored_nodes[index] {
//println!("Adjacent node: {:?}", adj_node);
explored_nodes[index] = true;
if current.0 == root_node {
queue.push_front((index, &adj_node));
} else {
queue.push_back((index, current.1)); // kinda needed for
// levels
}
}
}
index += 1;
}
level_size -= 1;
}
if found_target {
/* println!("FOUND TARGET! LEAPS: {:?}", leaps);
println!("queue after: {:?}", queue);*/
break;
}
}
if !found_target {
println!("{}", -1);
} else {
if leaps == 2000 { //emt miks tää mut trust
leaps = 0;
}
println!("{}", leaps + 2 * depth - 1);
}
}
}
}
fn set_leaps(start_column: bool, end_column: bool, leaps: &mut usize) {
if start_column && !end_column {
*leaps = min(*leaps, 1);
} else if !start_column && end_column {
*leaps = min(*leaps, 1);
} else if !start_column && !end_column {
*leaps = min(*leaps, 2);
} else {
*leaps = min(*leaps, 0);
}
}
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);
}*/
}
