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;

void bfs(vector<vector<int>> &vis, pi start) {
  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;
      q.push(ne);
    }
  }
}

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

  get(n, m);

  pi a;
  pi b;
  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);
  vc<vi> vis_b(n, vi(m, 0));
  bfs(vis_b, b);

  int ans = INT_MAX;
  if (vis_a[b.F][b.S]) {
    pril(1);
    return 0;
  } else {
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < m; ++j) {
        if (vis_a[i][j]) {
          for (int k = 0; k < n; ++k) {
            for (int z = 0; z < m; ++z) {
              if (vis_b[k][z]) {
                ans = min(ans, abs(i - k) + abs(j - z));
              }
            }
          }
        }
      }
    }
  }

  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