use std::collections::HashMap;
use std::collections::HashSet;
use std::collections::VecDeque;
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: HashMap<usize, HashSet<usize>>,
}
struct Path {
length: usize,
start_cols: Vec<usize>,
end_cols: Vec<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: HashMap::new(),
});
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.contains_key(&r2) {
let mut set = HashSet::new();
set.insert(i);
graph[r1].edges.insert(r2, set);
} else {
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 starting_columns: HashSet<usize> = HashSet::new();
let mut ending_columns: HashSet<usize> = HashSet::new();
let mut paths: Vec<Path> = Vec::new();
let mut found_target: bool = false;
// Then use BFS:
let mut queue: VecDeque<usize> = VecDeque::new();
let mut explored_nodes: HashSet<usize>;
let root_node = y1 - 1;
let target_node = y2 - 1;
explored_nodes.insert(root_node);
let mut parent_node = root_node;
}
}
// add parameters: length, starting cols, end cols.
fn bfs(graph: &Vec<Node>, queue: &mut VecDeque<usize>, explored_nodes: &mut HashSet<usize>) {
if queue.len() == 0 {
return;
}
let current: usize = *queue.front().unwrap();
queue.pop_front();
for adj_node in &graph[current].edges {
if !explored_nodes.contains(&adj_node.0) {
explored_nodes.insert(*adj_node.0);
queue.push_front(*adj_node.0);
}
}
bfs(graph, queue, explored_nodes);
}
}
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();
let j = map[i].edges.len();
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!("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);
}*/
}