Source Code
#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], mn[2][2] = {{oo, oo}, {oo, oo}};
char arr[510][510];
bool vis[510][510];

void bfs(int xx, int yy, int foo){
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < m; ++j){
            cost[i][j] = oo;
        }
    }
    queue< pair<int, int> > q;
    q.push({xx, yy});
    vis[xx][yy] = true;
    cost[xx][yy] = 0;
    while(!q.empty()){
        int x = q.front().first, y = q.front().second;
        q.pop();
        if(arr[x][y] == 'O'){
            mn[foo][0] = min(mn[foo][0], cost[x][y]);
        }
        if(arr[x][y] == 'B'){
            mn[foo][1] = min(mn[foo][1], 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;
        }
    }
}

void solve(){
    cin >> n >> m;
    bool o = false, b = false; 
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < m; ++j){
            cin >> arr[i][j];
            if(arr[i][j] == 'O'){
                o = true; 
            }
            if(arr[i][j] == 'B'){
                b = true; 
            }
        }
    }
    bfs(0, 0, 0);
    int ans = cost[n - 1][m - 1];
    memset(vis, false, sizeof(vis));
    bfs(n - 1, m - 1, 1);
    ans = min({ans, mn[0][0] + mn[1][1] + 1, mn[1][0] + mn[0][1] + 1});
    if(o){
        ans = min(ans, mn[0][0] + mn[1][0] + 2);
    }
    if(b){
        ans = min(ans, mn[0][1] + mn[1][1] + 2);
    }
    cout << (ans < 1e5 ? ans : -1);
}

int main(){
    int t = 1;
    // cin >> t;
    while(t--){
        solve();
    }
    return 0;
}
Copy
Malik Found a Portal Gun ItsAboudTime
GNU G++17
3 ms
872 KB
Wrong Answer