Sokkelo

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

int n,m;
vector<int> v[1000000];
string p[1000];
bool o[1000000];
bool k[1000000];

int A,B;

ll t=1e9;

vector<int> d;

void recA(int p){
    if(k[p])return;
    if(p==B){
        cout<<"1\n";
        exit(0);
    }
    k[p]=1;
    d.push_back(p);
    for(auto &i:v[p])recA(i);
}

void recB(int p){
    if(k[p])return;
    k[p]=1;
    for(auto &j:d){
            ll o=abs(p/m-j/m)+abs(p%m-j%m);
            t=min(o,t);
        }
    for(auto &i:v[p]){
        recB(i);
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin>>n>>m;
    for(int i=0;i<n;i++)cin>>p[i];
    for(int i=1;i<n-1;i++)for(int j=1;j<m-1;j++){
        if(p[i][j]=='.'||p[i][j]=='A'||p[i][j]=='B'){
            o[i*m+j]=1;
            if(j!=n-1&&p[i][j+1]=='.')v[i*m+j].push_back(i*m+j+1);
            if(j!=0&&p[i][j-1]=='.')v[i*m+j].push_back(i*m+j-1);
            if(i!=m-1&&p[i+1][j]=='.')v[i*m+j].push_back((i+1)*m+j);
            if(i!=0&&p[i-1][j]=='.')v[i*m+j].push_back((i-1)*m+j);
            if(p[i][j]=='A')A=i*m+j;
            if(p[i][j]=='B')B=i*m+j;
        }
    }
    recA(A);
    recB(B);
    cout<<t<<"\n";
}

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