#include<bits/stdc++.h>
using namespace std;
bool isValid(int x,int y,vector<vector<char>>& mat,vector<vector<bool>>& visited){
int n = mat.size();
int m = mat[0].size();
if(x >= n or y>=m or x<0 or y<0 or mat[x][y]=='#' or vis[x][y]){
return false;
}
return true;
}
vector<pair<int,int>> cords = {
{1,0},{0,1},{-1,0},{0,-1}
};
int funcTion(vector<vector<char>>& mat){
int n = mat.size();
int m = mat[0].size();
pair<int,int>B_initial = {-1,-1}; // initialization
pair<int,int>B_final = {-1,-1};
pair<int,int> O_initial = {-1,-1};
pair<int,int> O_final = {-1,-1};
for(int i=0;i<n;i++) for(int j=0;j<m;j++){
if(mat[i][j] == 'B'){
if(B_initial.first != -1 and B_initial.second != -1){
B_final.first = i;
B_final.second = j;
}
else{
B_initial.first = i;
B_initial.second = j;
}
} // cords. of the B
if(O_initial.first != -1 and O_initial.second != -1){
O_final.first = i;
O_final.second = j;
}
else{
O_initial.first = i;
O_initial.second = j;
}
} // cords. of the O
if(mat[0][0] =='#' or mat[n-1][m-1] == '#'){
return -1;
} // already the cell is blocked
vector<vector<bool>> visited(n,vector<bool>(m,false));
queue<tuple<int,int,int>> q;
q.push({0,0,0});
visited[0][0] = true;
while(!q.empty()){
int sz = q.size();
while(sz--){
tuple current = q.front(); q.pop();
int x = get<0>(current);
int y = get<1>(current);
int d = get<2>(current);
if(x == n-1 and y == m-1 and mat[x][y] == '.'){
return d;
}
for(auto [dx,dy]:cords){
if(isValid(x+dx,y+dy,mat,visited)){
if(mat[x+dx][y+dy] == 'B' or (x+dx == B_initial.first and y+dy == B_initial.second)){
q.push({B_final.first,B_final.second,d+1});
visited[B_final.first][B_final.second] = true;
}
}
else if(isValid(x+dx,y+dy,mat,visited)){
if(mat[x+dx][y+dy] == 'O' or (x+dx == O_initial.first and y+dy == O_initial.second)){
q.push({O_final.first,O_final.second,d+1});
visited[O_final.first][O_final.second] = true;
}
}
else{
q.push({x+dx,y+dy,d+1});
visited[x+dx][y+dy] = true;
}
}
}
}
return -1;
}
void solve(){
int n,m;
cin>>n>>m;
vector<vector<char>>mat(n,vector<char>(m));
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
cin>> mat[i][j];
}
}
cout << funcTion(mat);
return;
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
solve();
return 0;
}
Copy