Source Code
#include <bits/stdc++.h>
using namespace std;
#define ll long long
string Mv = "RLDU";
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
const int N = 5e2 + 2;
int n, m;
int ans = 1e9;
int mnO = 1e9;
int mnB = 1e9;
int cost[2][N][N];
char g[N][N];
void go(int a, int b, int id = 0) {
    cost[id][a][b] = 0;
    queue<array<int, 2>> q;
    q.push({a, b});
    while (q.size()) {
        auto src = q.front();
        q.pop();
        for (int i = 0; i < 4; ++i) {
            int x = src[0] + dx[i];
            int y = src[1] + dy[i];
            if (min(x, y) < 0 || x >= n || y >= m || cost[id][x][y] != -1 || g[x][y] == '#')
                continue;
            cost[id][x][y] = cost[id][src[0]][src[1]] + 1;
            if (id) {
                if (g[x][y] == 'B' && mnO != 1e9) ans = min(ans, cost[id][x][y] + mnO + 1);
                if (g[x][y] == 'O' && mnB != 1e9) ans = min(ans, cost[id][x][y] + mnB + 1);
            } 
            q.push({x, y});
        }
    }
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    memset(cost, -1, sizeof(cost));
    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> g[i][j];
        }
    }
    go(n - 1, m - 1);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (g[i][j] == 'O') {
                mnO = min(mnO, cost[0][i][j]);   
            } else if (g[i][j] == 'B') {
                mnB = min(mnB, cost[0][i][j]);   
            }
        }
    }
    go(0, 0, 1);
    if (cost[1][n - 1][m - 1] != -1) {
        ans = min(ans, cost[1][n - 1][m - 1]);
    }
    if (ans == 1e9) ans = -1;
    cout << ans << '\n';
    return 0;
}
Copy
Malik Found a Portal Gun Heartbeat
GNU G++17
4 ms
2.7 MB
Wrong Answer