use std::io;
use std::collections::{HashMap, HashSet, VecDeque};
use rand::{random, random_range};
use std::time::{SystemTime, UNIX_EPOCH};
type NodeID = (usize, usize);
fn main() {
let mut input = String::new();
io::stdin().read_line(&mut input).expect("Failed to read input");
let startdata: Vec<usize> = input.split_whitespace().map(|e| e.parse::<usize>().unwrap()).collect();
let mut grid: Vec<Vec<bool>> = vec!();
for row in 0..startdata[0] {
let mut newrow: Vec<bool> = vec!();
let mut rowinput = String::new();
io::stdin().read_line(&mut rowinput).expect("Failed to read input");
for c in rowinput.into_bytes().into_iter() {
if c == 46 {
newrow.push(true);
} else {
newrow.push(false);
}
}
grid.push(newrow);
}
//dbg!(&grid);
for _q in 0..startdata[2] {
let mut questioninput = String::new();
io::stdin().read_line(&mut questioninput).expect("Failed to read input");
let start = SystemTime::now().duration_since(UNIX_EPOCH).unwrap().as_nanos();
let questiondata: Vec<usize> = questioninput.split_whitespace().map(|e| e.parse::<usize>().unwrap()-1).collect();
let source: NodeID = (questiondata[0], questiondata[1]);
let destination: NodeID = (questiondata[2], questiondata[3]);
/*let y1 = random_range(0..startdata[0]);
let y2 = random_range(0..startdata[0]);
let x1 = random_range(0..startdata[1]);
let x2 = random_range(0..startdata[1]);
let source = (y1, x1);
let destination = (y2, x2);*/
if source == destination {
println!("0");
continue;
}
let mut distancehash: HashMap<(NodeID, NodeID), usize> = HashMap::new();
let mut checkedset: HashSet<NodeID> = HashSet::new();
distancehash.insert((source, source), 0);
distancehash.insert((destination, destination), 0);
let mut sourcequeue: VecDeque<NodeID> = VecDeque::new();
sourcequeue.push_front(source);
let mut destqueue: VecDeque<NodeID> = VecDeque::new();
destqueue.push_front(destination);
checkedset.insert(source);
checkedset.insert(destination);
'outer: while sourcequeue.len() != 0 && destqueue.len() != 0 {
let node = sourcequeue.pop_back().unwrap();
let dist = *distancehash.get(&(source, node)).unwrap();
let destnode = destqueue.pop_back().unwrap();
let destdist = *distancehash.get(&(destination, destnode)).unwrap();
dbg!(&node);
for row in 0..grid.len() {
if row == node.0 {
for cell in 0..node.1 {
if grid[row][cell] {
let neighbor = (row, cell);
match distancehash.get(&(source, neighbor)) {
Some(_) => {}
None =>{
distancehash.entry((source, neighbor)).or_insert(dist+1);
sourcequeue.push_front(neighbor);
if !checkedset.insert(neighbor) {
let desttoneighbor = distancehash[&(destination, neighbor)];
distancehash.insert((source, destination), dist+1+desttoneighbor);
break 'outer;
}
}
}
if neighbor == destination {
break 'outer;
}
}
}
for cell in (node.1+1)..grid[row].len() {
if grid[row][cell] {
let neighbor = (row, cell);
match distancehash.get(&(source, neighbor)) {
Some(_) => {}
None =>{
distancehash.entry((source, neighbor)).or_insert(dist+1);
sourcequeue.push_front(neighbor);
if !checkedset.insert(neighbor) {
let desttoneighbor = distancehash[&(destination, neighbor)];
distancehash.insert((source, destination), dist+1+desttoneighbor);
break 'outer;
}
}
}
if neighbor == destination {
break 'outer;
}
}
}
} else {
if grid[row][node.1] {
let neighbor = (row, node.1);
match distancehash.get(&(source, neighbor)) {
Some(_) => {}
None => {
distancehash.entry((source, neighbor)).or_insert(dist+1);
sourcequeue.push_front(neighbor);
if !checkedset.insert(neighbor) {
let desttoneighbor = distancehash[&(destination, neighbor)];
distancehash.insert((source, destination), dist+1+desttoneighbor);
break 'outer;
}
}
}
if neighbor == destination {
break 'outer;
}
}
}
}
for row in 0..grid.len() {
if row == destnode.0 {
for cell in 0..destnode.1 {
if grid[row][cell] {
let neighbor = (row, cell);
match distancehash.get(&(destination, neighbor)) {
Some(_) => {}
None =>{
distancehash.entry((destination, neighbor)).or_insert(destdist+1);
destqueue.push_front(neighbor);
if !checkedset.insert(neighbor) {
let sourcetoneighbor = distancehash[&(source, neighbor)];
distancehash.insert((source, destination), destdist+sourcetoneighbor+1);
break 'outer;
}
}
}
}
}
for cell in (destnode.1+1)..grid[row].len() {
if grid[row][cell] {
let neighbor = (row, cell);
match distancehash.get(&(destination, neighbor)) {
Some(_) => {}
None =>{
distancehash.entry((destination, neighbor)).or_insert(destdist+1);
destqueue.push_front(neighbor);
if !checkedset.insert(neighbor) {
let sourcetoneighbor = distancehash[&(source, neighbor)];
distancehash.insert((source, destination), destdist+sourcetoneighbor+1);
break 'outer;
}
}
}
}
}
} else {
if grid[row][destnode.1] {
let neighbor = (row, destnode.1);
match distancehash.get(&(destination, neighbor)) {
Some(_) => {}
None => {
distancehash.entry((destination, neighbor)).or_insert(destdist+1);
destqueue.push_front(neighbor);
if !checkedset.insert(neighbor) {
let sourcetoneighbor = distancehash[&(source, neighbor)];
distancehash.insert((source, destination), destdist+sourcetoneighbor+1);
break 'outer;
}
}
}
}
}
}
}
match distancehash.get(&(source, destination)) {
Some(s) => {println!("{}", s);},
None => {println!("-1");}
}
let end = SystemTime::now().duration_since(UNIX_EPOCH).unwrap().as_nanos();
println!("{}", end-start);
}
}