Sokkelo

#include <bits/stdc++.h>
using namespace std;
template <typename... Args>
auto create(size_t n, Args&&... args) {
  if constexpr (sizeof...(args) == 1) {
    return vector(n, args...);
  } else {
    return vector(n, create(args...));
  }
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  string g[n];
  for (auto &r : g) {
    cin >> r;
  }
  int c = 0;
  auto comp = create(n, m, 0);
  function<void(int, int)> dfs = [&](int i, int j) {
    if (i < 0 || j < 0 || i >= n || j >= m) return;
    if (g[i][j] == '#' || comp[i][j]) return;
    comp[i][j] = c;
    dfs(i + 1, j);
    dfs(i - 1, j);
    dfs(i, j + 1);
    dfs(i, j - 1);
  };
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < m; ++j) {
      if (!comp[i][j] && g[i][j] != '#') {
        ++c;
        dfs(i, j);
      }
    }
  }
  int ai = -1, aj = -1, bi = -1, bj = -1;
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < m; ++j) {
      if (g[i][j] == 'A') {
        ai = i;
        aj = j;
      } else if (g[i][j] == 'B') {
        bi = i;
        bj = j;
      }
    }
  }
  if (comp[ai][aj] == comp[bi][bj]) {
    cout << 1 << endl;
  } else {
    bool ng[n + m][n + m] {};
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < m; ++j) {
        if (comp[i][j] == comp[ai][aj]) {
          ng[i + j][i - j + m - 1] = 1;
        }
      }
    }
    auto ngs = create(n + m, n + m, 0);
    for (int i = 0; i < n + m - 1; ++i) {
      for (int j = 0; j < n + m - 1; ++j) {
        ngs[i + 1][j + 1] = ngs[i + 1][j] + ngs[i][j + 1] - ngs[i][j] + ng[i][j];
      }
    }
    auto query = [&](int i0, int j0, int i1, int j1) {
      i0 = max(i0, 0);
      j0 = max(j0, 0);
      i1 = min(i1, n + m - 1);
      j1 = min(j1, n + m - 1);
      return ngs[i1][j1] - ngs[i0][j1] - ngs[i1][j0] + ngs[i0][j0];
    };
    auto test = [&](int d) {
      auto check = [&](int i, int j) {
        return query(i - d, j - d, i + d + 1, j + d + 1);
      };
      for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
          if (comp[i][j] == comp[bi][bj]) {
            int ni = i + j;
            int nj = i - j + m - 1;
            if (check(ni, nj)) {
              return 1;
            }
          }
        }
      }
      return 0;
    };
    int l = 0, r = n + m;
    while (l < r) {
      int mp = (l + r) / 2;
      if (test(mp)) r = mp;
      else l = mp + 1;
    }
    cout << l << endl;
  }
}

Test 1

Group: 1, 2

Verdict: ACCEPTED

Test 2

Group: 1, 2

Verdict: ACCEPTED

Test 3

Group: 1, 2

Verdict: ACCEPTED

Test 4

Group: 2

Verdict: ACCEPTED

Test 5

Group: 2

Verdict: ACCEPTED

Test 6

Group: 2

Verdict: ACCEPTED

Test 7

Group: 1, 2

Verdict: ACCEPTED

Test 8

Group: 2

Verdict: ACCEPTED

Test 9

Group: 2

Verdict: ACCEPTED

Test 10

Group: 1, 2

Verdict: ACCEPTED

Test 11

Group: 2

Verdict: ACCEPTED

Test 12

Group: 1, 2

Verdict: ACCEPTED

Test 13

Group: 2

Verdict: ACCEPTED

Test 14

Group: 1, 2

Verdict: ACCEPTED

Test 15

Group: 2

Verdict: ACCEPTED

Test 16

Group: 2

Verdict: ACCEPTED

Test 17

Group: 2

Verdict: ACCEPTED