Source Code
#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
Malik Found a Portal Gun YazanIstatiyeh
GNU G++17
24 ms
3.1 MB
Accepted