#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
const int N=500;
const int dx[]={0,0,1,-1};
const int dy[]={1,-1,0,0};
int n,m;
vector<vector<char>>grid(N,vector<char>(N));
inline bool valid(int i, int j){
return i>=0&&j>=0&&i<n&&j<m&&grid[i][j]!='#';
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin>>n>>m;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
cin>>grid[i][j];
}
}
vector<vector<int>>dis(n,vector<int>(m,-1));
queue<pair<int,int>>q;
q.push({n-1,m-1});
dis[n-1][m-1]=0;
while(!q.empty()){
pair<int,int>cur=q.front();
q.pop();
for(int dir=0;dir<4;dir++){
int di=cur.first+dx[dir];
int dj=cur.second+dy[dir];
if(!valid(di,dj)) continue;
if(dis[di][dj]!=-1) continue;
dis[di][dj]=dis[cur.first][cur.second]+1;
q.push({di,dj});
}
}
pair<int,int>closeO={1e9,1e9},closeB={1e9,1e9};
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(dis[i][j]==-1) continue;
if(grid[i][j]=='O'){
if(closeO.first==(int)1e9||dis[i][j]<dis[closeO.first][closeO.second]){
closeO={i,j};
}
} else if(grid[i][j]=='B'){
if(closeB.first==(int)1e9||dis[i][j]<dis[closeB.first][closeB.second]){
closeB={i,j};
}
}
}
}
while(!q.empty()) q.pop();
dis=vector<vector<int>>(n,vector<int>(m,-1));
q.push({0,0});
dis[0][0]=0;
while(!q.empty()){
pair<int,int>cur=q.front();
q.pop();
for(int dir=0;dir<4;dir++){
int di=cur.first+dx[dir];
int dj=cur.second+dy[dir];
if(!valid(di,dj)) continue;
if(dis[di][dj]!=-1) continue;
dis[di][dj]=dis[cur.first][cur.second]+1;
q.push({di,dj});
}
if(grid[cur.first][cur.second]=='B'&&closeO.first!=(int)1e9){
if(dis[closeO.first][closeO.second]==-1){
dis[closeO.first][closeO.second]=dis[cur.first][cur.second]+1;
q.push(closeO);
}
}
if(grid[cur.first][cur.second]=='O'&&closeB.first!=(int)1e9){
if(dis[closeB.first][closeB.second]==-1){
dis[closeB.first][closeB.second]=dis[cur.first][cur.second]+1;
q.push(closeB);
}
}
}
cout<<dis[n-1][m-1];
}
Copy