Sokkelo

#include <bits/stdc++.h>
using namespace std;

#define F first
#define S second
#define pb push_back
#define vc vector
#define rep(i, a, b) for (int i = a; i < b; ++i)
#define tra(a, x) for (auto &a : x)
#define sz(x) (int)(x).size()
#define all(x) x.begin(), x.end()

template <typename... T> void get(T &...args) { ((cin >> args), ...); }
template <typename... T> void pri(T &&...args) { ((cout << args << " "), ...); }
template <typename... T> void pril(T &&...args) {
  ((cout << args << " "), ...);
  cout << '\n';
}

using ll = long long;
using vi = vc<int>;
using vll = vc<ll>;
using pi = pair<int, int>;

const ll LINF = 1e18;
const int INF = 1e9;
const ll mod = 1e9 + 7;
const int N = 1010;

char grid[N][N];
int x[4] = {-1, 0, 1, 0};
int y[4] = {0, 1, 0, -1};
int n, m;
vector<pair<pi, bool>> visited_points;
pi a, b;

void bfs(vector<vector<int>> &vis, pi start, bool isa) {
  queue<pi> q;
  q.push(start);
  vis[start.F][start.S] = 1;

  while (!q.empty()) {
    auto s = q.front();
    q.pop();
    rep(i, 0, 4) {
      pi ne = {s.F + x[i], s.S + y[i]};
      if (ne.F < 0 || ne.F >= n || ne.S < 0 || ne.S >= m)
        continue;
      if (vis[ne.F][ne.S] == 1)
        continue;
      if (grid[ne.F][ne.S] == '#')
        continue;
      vis[ne.F][ne.S] = 1;
      visited_points.pb({ne, isa});
      q.push(ne);
    }
  }
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);

  get(n, m);

  rep(i, 0, n) {
    rep(j, 0, m) {
      get(grid[i][j]);
      if (grid[i][j] == 'A') {
        a = {i, j};
      } else if (grid[i][j] == 'B') {
        b = {i, j};
      }
    }
  }
  vc<vi> vis_a(n, vi(m, 0));
  bfs(vis_a, a, true);
  vc<vi> vis_b(n, vi(m, 0));
  bfs(vis_b, b, false);

  int ans = INT_MAX;
  if (vis_a[b.F][b.S]) {
    pril(1);
    return 0;
  } else {
    for (int i = 0; i < sz(visited_points); ++i) {
      for (int j = i + 1; j < sz(visited_points); ++j) {
        if (visited_points[i].S != visited_points[j].S) {
          auto ap = visited_points[i].F;
          auto bp = visited_points[j].F;

          ans = min(ans, abs(ap.F - bp.F) + abs(ap.S - bp.S));
        }
      }
    }
  }

  pril(ans);
}

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: TIME LIMIT EXCEEDED

Test 6

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 7

Group: 1, 2

Verdict: ACCEPTED

Test 8

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 9

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 10

Group: 1, 2

Verdict: ACCEPTED

Test 11

Group: 2

Verdict: TIME LIMIT EXCEEDED

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