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 (mnO != 1e9) ans = min(ans, cost[id][x][y] + mnB + 2);
                }
                if (g[x][y] == 'O' && mnB != 1e9) {
                    ans = min(ans, cost[id][x][y] + mnB + 1);
                    if (mnB != 1e9) ans = min(ans, cost[id][x][y] + mnO + 2);
                }
            }
            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]);
            }
        }
    }
    // for (int i = 0; i < n; ++i) {
    //     for (int j = 0; j < m; ++j) {
    //         cout << cost[0][i][j] << " \n"[j + 1 == m];
    //     }
    // }
    go(0, 0, 1);
    if (cost[1][n - 1][m - 1] != -1) {
        assert(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
24 ms
3.1 MB
Wrong Answer