Sokkelo

#include <bits/stdc++.h>
 
typedef long long ll;
 
#define M 1000000007
#define N (1 << 18)
 
using namespace std;
 
string mp[1001];
bool vis[1001][1001];
bool vis2[1001][1001];
int dst[1001][1001];
 
int dirs[4][2] = {
    {-1, 0},
    {0, -1},
    {1, 0},
    {0, 1}
};
 
void dfs(int y, int x) {
    if (vis[y][x]) return;
    vis[y][x] = 1;
 
    for (int k = 0; k < 4; ++k) {
        int ny = y + dirs[k][0];
        int nx = x + dirs[k][1];
 
        if (mp[ny][nx] != '#') {
            dfs(ny, nx);
        }
    }
}
 
void dfs2(int y, int x) {
    if (vis2[y][x]) return;
    vis2[y][x] = 1;
 
    for (int k = 0; k < 4; ++k) {
        int ny = y + dirs[k][0];
        int nx = x + dirs[k][1];
 
        if (mp[ny][nx] != '#') {
            dfs2(ny, nx);
        }
    }
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        cin >> mp[i];
    }
 
    pair<int, int> a = {-1, -1};
    pair<int, int> b = {-1, -1};
 
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (mp[i][j] == 'A') {
                a = {i, j};
            }
            else if (mp[i][j] == 'B') {
                b = {i, j};
            }
        }
    }
 
    dfs(a.first, a.second);
 
    if (vis[b.first][b.second]) {
        cout << 1 << "\n";
        return 0;
    }
 
    queue<pair<int, int>> q;
 
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (!vis[i][j]) {
                dst[i][j] = 1e9;
            } else {
                q.push({i, j});
            }
            //cout << (dst[i][j] == 0 ? 0 : 1);
        }
        //cout << endl;
    }
 
    while (!q.empty()) {
        auto p = q.front(); q.pop();
 
        int x = p.second;
        int y = p.first;
 
        for (int k = 0; k < 4; ++k) {
            int nx = x + dirs[k][1];
            int ny = y + dirs[k][0];
 
            if (nx >= 0 && ny >= 0 && nx < m && ny < n && dst[y][x] + 1 < dst[ny][nx]) {
                dst[ny][nx] = dst[y][x] + 1;
                q.push({ny, nx});
            }
        }
    }
 
    dfs2(b.first, b.second);
 
    int ans = 1e9;
 
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (vis2[i][j]) {
                ans = min(ans, dst[i][j]);
                //cout << i << ", " << j << endl;
            }
        }
    }
    if (ans > n * m || ans < 2) exit(-1);
    cout << ans << "\n";
 
    return 0;
}

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