#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