#include <bits/stdc++.h>
using namespace std;
const int oo = 1000000010;
const int N = 100010;
const int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1};
int n, m, cost[510][510];
char arr[510][510];
bool vis[510][510];
int bfs1(){
queue< pair<int, int> > q;
q.push({0, 0});
cost[0][0] = 0;
vis[0][0] = true;
while(!q.empty()){
int x = q.front().first, y = q.front().second;
q.pop();
for(int i = 0; i < 4; ++i){
int nx = x + dx[i], ny = y + dy[i];
if(nx < 0 || nx >= n || ny < 0 || ny >= m){
continue;
}
if(vis[nx][ny]){
continue;
}
if(arr[nx][ny] == '#'){
continue;
}
q.push({nx, ny});
vis[nx][ny] = true;
cost[nx][ny] = cost[x][y] + 1;
}
}
return cost[n - 1][m - 1];
}
int bfs2(int xx, int yy, char c){
memset(vis, false, sizeof(vis));
queue< pair<int, int> > q;
q.push({xx, yy});
vis[xx][yy] = true;
cost[xx][yy] = 0;
int res = oo;
while(!q.empty()){
int x = q.front().first, y = q.front().second;
q.pop();
if(arr[x][y] == c){
res = min(res, cost[x][y]);
}
for(int i = 0; i < 4; ++i){
int nx = x + dx[i], ny = y + dy[i];
if(nx < 0 || nx >= n || ny < 0 || ny >= m){
continue;
}
if(vis[nx][ny]){
continue;
}
if(arr[nx][ny] == '#'){
continue;
}
q.push({nx, ny});
vis[nx][ny] = true;
cost[nx][ny] = cost[x][y] + 1;
}
}
return res;
}
void solve(){
cin >> n >> m;
for(int i = 0; i < n; ++i){
for(int j = 0; j < m; ++j){
cin >> arr[i][j];
}
}
for(int i = 0; i < n; ++i){
for(int j = 0; j < m; ++j){
cost[i][j] = oo;
}
}
int ans = min({bfs1(), bfs2(0, 0, 'O') + bfs2(n - 1, m - 1, 'B') + 1, bfs2(0, 0, 'B') + bfs2(n - 1, m - 1, 'O') + 1});
cout << (ans < 2500 ? ans : -1);
}
int main(){
int t = 1;
//cin >> t;
while(t--){
solve();
}
return 0;
}
Copy