use std::{
collections::HashSet,
io::{stdin, BufRead, BufReader},
};
fn main() {
let mut stdin = BufReader::new(stdin());
let mut cur_line = String::new();
stdin.read_line(&mut cur_line).unwrap();
let mut nums = cur_line
.split_whitespace()
.map(|s| s.parse::<usize>().unwrap());
let n = nums.next().unwrap();
let m = nums.next().unwrap();
let maze = fill_maze(n, m);
return;
println!("{}", get_dist(maze, n, m));
}
fn get_dist(mut maze: Vec<Vec<u8>>, n: usize, m: usize) -> usize {
let mut neighbors_a = HashSet::new();
for y in 1..n - 1 {
for x in 1..m - 1 {
if maze[y][x] == b'A' {
if y - 1 > 0 && maze[y - 1][x] != b'A' {
neighbors_a.insert((x, y - 1));
}
if y + 1 < n - 1 && maze[y + 1][x] != b'A' {
neighbors_a.insert((x, y + 1));
}
if x - 1 > 0 && maze[y][x - 1] != b'A' {
neighbors_a.insert((x - 1, y));
}
if x + 1 < m - 1 && maze[y][x + 1] != b'A' {
neighbors_a.insert((x + 1, y));
}
}
}
}
for c in 1.. {
let mut new_neighbors = HashSet::new();
for &(x, y) in &neighbors_a {
if maze[y][x] == b'B' {
return c;
}
maze[y][x] = b'A';
if y - 1 > 0 && maze[y - 1][x] != b'A' {
new_neighbors.insert((x, y - 1));
}
if y + 1 < n - 1 && maze[y + 1][x] != b'A' {
new_neighbors.insert((x, y + 1));
}
if x - 1 > 0 && maze[y][x - 1] != b'A' {
new_neighbors.insert((x - 1, y));
}
if x + 1 < m - 1 && maze[y][x + 1] != b'A' {
new_neighbors.insert((x + 1, y));
}
}
neighbors_a = new_neighbors;
}
0
}
fn fill_maze(n: usize, m: usize) -> Vec<Vec<u8>> {
let mut stdin = BufReader::new(stdin());
let mut maze = Vec::with_capacity(n);
for _ in 0..n {
let mut cur_line = String::new();
stdin.read_line(&mut cur_line).unwrap();
maze.push(cur_line.into_bytes());
}
let mut neighbors_a = HashSet::new();
let mut neighbors_b = HashSet::new();
for y in 1..n - 1 {
for x in 1..m - 1 {
if maze[y][x] == b'A' {
// if maze[y - 1][x] == b'.' {
// neighbors_a.insert((x, y - 1));
// }
// if maze[y + 1][x] == b'.' {
// neighbors_a.insert((x, y + 1));
// }
// if maze[y][x - 1] == b'.' {
// neighbors_a.insert((x - 1, y));
// }
// if maze[y][x + 1] == b'.' {
// neighbors_a.insert((x + 1, y));
// }
}
if maze[y][x] == b'B' {
// if maze[y - 1][x] == b'.' {
// neighbors_b.insert((x, y - 1));
// }
// if maze[y + 1][x] == b'.' {
// neighbors_b.insert((x, y + 1));
// }
// if maze[y][x - 1] == b'.' {
// neighbors_b.insert((x - 1, y));
// }
// if maze[y][x + 1] == b'.' {
// neighbors_b.insert((x + 1, y));
// }
}
}
}
return Vec::new();
loop {
let mut new_neighbors_a = HashSet::new();
let mut new_neighbors_b = HashSet::new();
for &(x, y) in &neighbors_a {
// maze[y][x] = b'A';
if y > 0 && maze[y - 1][x] == b'.' && !neighbors_a.contains(&(x, y - 1)) {
// new_neighbors_a.insert((x, y - 1));
}
if y < n - 1 && maze[y + 1][x] == b'.' && !neighbors_a.contains(&(x, y + 1)) {
// new_neighbors_a.insert((x, y + 1));
}
if x > 0 && maze[y][x - 1] == b'.' && !neighbors_a.contains(&(x - 1, y)) {
// new_neighbors_a.insert((x - 1, y));
}
if x < m - 1 && maze[y][x + 1] == b'.' && !neighbors_a.contains(&(x + 1, y)) {
// new_neighbors_a.insert((x + 1, y));
}
}
// for &(x, y) in &neighbors_b {
// maze[y][x] = b'B';
// if maze[y - 1][x] == b'.' && !neighbors_b.contains(&(x, y - 1)) {
// new_neighbors_b.insert((x, y - 1));
// }
// if maze[y + 1][x] == b'.' && !neighbors_b.contains(&(x, y + 1)) {
// new_neighbors_b.insert((x, y + 1));
// }
// if maze[y][x - 1] == b'.' && !neighbors_b.contains(&(x - 1, y)) {
// new_neighbors_b.insert((x - 1, y));
// }
// if maze[y][x + 1] == b'.' && !neighbors_b.contains(&(x + 1, y)) {
// new_neighbors_b.insert((x + 1, y));
// }
// }
if new_neighbors_a.is_empty() && new_neighbors_b.is_empty() {
break maze;
}
neighbors_a = new_neighbors_a;
neighbors_b = new_neighbors_b;
}
}