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;


ll ite1(int y,int x,ll d){
    if(p[y][x]=='A'){
        return d;
    }
    if(d>t)return 1e9;
    ll e=1e9;
    if(y!=0)e=min(e,ite1(y-1,x,d+1));
    if(x!=m-1)e=min(e,ite1(y,x+1,d+1));
    return e;
}
ll ite2(int y,int x,ll d){
    if(p[y][x]=='A'){
        return d;
    }
    if(d>t)return 1e9;
    ll e=1e9;
    if(x!=m-1)e=min(e,ite2(y,x+1,d+1));
    if(y!=n-1)e=min(e,ite2(y+1,x,d+1));
    return e;
}
ll ite3(int y,int x,ll d){
    if(p[y][x]=='A'){
        return d;
    }
    if(d>t)return 1e9;
    ll e=1e9;
    if(y!=n-1)e=min(e,ite3(y+1,x,d+1));
    if(x!=0)e=min(e,ite3(y,x-1,d+1));
    return e;
}
ll ite4(int y,int x,ll d){
    if(p[y][x]=='A'){
        return d;
    }
    if(d>t)return 1e9;
    ll e=1e9;
    if(x!=0)e=min(e,ite4(y,x-1,d+1));
    if(y!=0)e=min(e,ite4(y-1,x,d+1));
    return e;
}

void recA(int u){
    if(k[u])return;
    if(u==B){
        cout<<"1\n";
        exit(0);
    }
    k[u]=1;
    p[u/m][u%m]='A';
    for(auto &i:v[u])recA(i);
}

void recB(int p){
    if(k[p])return;
    k[p]=1;
    t=min(t,ite1(p/m-1,p%m,1));
    t=min(t,ite2(p/m,p%m+1,1));
    t=min(t,ite3(p/m+1,p%m,1));
    t=min(t,ite4(p/m,p%m-1,1));
    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: TIME LIMIT EXCEEDED

Test 14

Group: 1, 2

Verdict: ACCEPTED

Test 15

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 16

Group: 2

Verdict: ACCEPTED

Test 17

Group: 2

Verdict: TIME LIMIT EXCEEDED