#include <bits/stdc++.h>

/*
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
*/
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define rep(i,l,r) for (int i=l;i<=r;i++)
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define ll long long
#define ull unsigned long long
#define mod 1000000007
#define nul(x) memset((x),0,sizeof((x)))
#define random_jbt mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

using namespace std;

int n,m;
char d[510][510];
int cnt[510][510];
set<char>ok[510][510];
int r[6];
priority_queue<pair<pair<int,pair<int,int>>,char>>q;
/*
K - King
B - Bishop
T - Top
N - Knight
Q - Queen
*/

void proveri(int i,int j,int val,char c){
    if (i<1 or i>n or j<1 or j>m)return;
    if (val>cnt[i][j])return;
    if (d[i][j]=='#')return;

    cnt[i][j]=val;
    q.push({{-val,{i,j}},c});
}

void uradi(int x,int y,char c,int val){

    if (c=='K'){
        for (int i=x-1;i<=x+1;i++){
            for (int j=y-1;j<=y+1;j++){
                if (i==x and j==y)continue;
                if (i<1 or i>n or j<1 or j>m)continue;
                if (val>cnt[i][j])continue;
                if (d[i][j]=='#')continue;

                cnt[i][j]=val;
                q.push({{-val,{i,j}},c});
            }
        }
        return;
    }

    if (c=='B' or c=='Q'){
        int i,j;

        //gore-levo
        for (int raz=1;;raz++){
            i = x-raz;
            j = y-raz;

            if (i<1 or i>n or j<1 or j>m)break;
            if (i==x and j==y)continue;
            if (val>cnt[i][j])continue;
            if (d[i][j]=='#')break;

            cnt[i][j]=val;
            q.push({{-val,{i,j}},c});
        }
        //gore-desno
        for (int raz=1;;raz++){
            i = x-raz;
            j = y+raz;

            if (i<1 or i>n or j<1 or j>m)break;
            if (i==x and j==y)continue;
            if (val>cnt[i][j])continue;
            if (d[i][j]=='#')break;

            cnt[i][j]=val;
            q.push({{-val,{i,j}},c});
        }
        //dole-levo
        for (int raz=1;;raz++){
            i = x+raz;
            j = y-raz;

            if (i<1 or i>n or j<1 or j>m)break;
            if (i==x and j==y)continue;
            if (val>cnt[i][j])continue;
            if (d[i][j]=='#')break;

            cnt[i][j]=val;
            q.push({{-val,{i,j}},c});
        }
        //dole-desno
        for (int raz=1;;raz++){
            i = x+raz;
            j = y+raz;

            if (i<1 or i>n or j<1 or j>m)break;
            if (i==x and j==y)continue;
            if (val>cnt[i][j])continue;
            if (d[i][j]=='#')break;

            cnt[i][j]=val;
            q.push({{-val,{i,j}},c});
        }
    }

    if (c=='T' or c=='Q'){
        //gore
        int i,j;
        for (int raz=1;;raz++){
            i = x+raz;

            if (i<1 or i>n or j<1 or j>m)break;
            if (i==x and j==y)continue;
            if (val>cnt[i][j])continue;
            if (d[i][j]=='#')break;

            cnt[i][j]=val;
            q.push({{-val,{i,j}},c});
        }
        //dole
        for (int raz=1;;raz++){
            i = x-raz;

            if (i<1 or i>n or j<1 or j>m)break;
            if (i==x and j==y)continue;
            if (val>cnt[i][j])continue;
            if (d[i][j]=='#')break;

            cnt[i][j]=val;
            q.push({{-val,{i,j}},c});
        }
        //levo
        for (int raz=1;;raz++){
            j = y-raz;

            if (i<1 or i>n or j<1 or j>m)break;
            if (i==x and j==y)continue;
            if (val>cnt[i][j])continue;
            if (d[i][j]=='#')break;

            cnt[i][j]=val;
            q.push({{-val,{i,j}},c});
        }
        //desno
        for (int raz=1;;raz++){
            j = y+raz;

            if (i<1 or i>n or j<1 or j>m)break;
            if (i==x and j==y)continue;
            if (val>cnt[i][j])continue;
            if (d[i][j]=='#')break;

            cnt[i][j]=val;
            q.push({{-val,{i,j}},c});
        }
    }

    if (c=='N'){
        proveri(x-1,y-2,val,c);
        proveri(x-2,y-1,val,c);
        proveri(x-2,y+1,val,c);
        proveri(x-1,y+2,val,c);
        proveri(x+1,y-2,val,c);
        proveri(x+2,y-1,val,c);
        proveri(x+2,y+1,val,c);
        proveri(x+1,y+2,val,c);
    }
}

void rand_input(){
    random_jbt;
    n = m = 500;

    vector<char>v;
    for (int i=1;i<=3;i++)v.pb('.');
    v.pb('#');

    for (int i=1;i<=n;i++){
        for (int j=1;j<=m;j++){
            d[i][j]='.';

            if (i==1 and j==1)d[i][j]='.';
            if (i==n and j==m)d[i][j]='.';
            cnt[i][j]=5000*5000;
        }
    }
}
void input(){
    cin>>n>>m;
    for (int i=1;i<=n;i++){
        for (int j=1;j<=m;j++){
            cin>>d[i][j];
            cnt[i][j]=5000*5000;
        }
    }
}

int main(){
    ios;

    input();

    int brojac=0;
    q.push({{0,{1,1}},'K'});
    while(!q.empty()){
        brojac++;
        //prenesi vrednosti
        int br = - (q.top().fi.fi);
        int x = q.top().fi.se.fi;
        int y = q.top().fi.se.se;
        char c = q.top().se;
        q.pop();

        //testiraj edge case-ove
        if (br > cnt[x][y] or d[x][y]=='#')continue;
        auto it=ok[x][y].find(c);
        if (it!=ok[x][y].end())continue;

        ok[x][y].insert(c);
        cnt[x][y]=br;

        //deklarisi ko ima penalty-free pass
        for (int i=1;i<=5;i++)r[i]=i;
        if (c=='K')r[1]=0;
        if (c=='B')r[2]=0;
        if (c=='T')r[3]=0;
        if (c=='N')r[4]=0;
        if (c=='Q')r[5]=0;


        uradi(x,y,'K',br+r[1]+1);
        uradi(x,y,'B',br+r[2]+1);
        uradi(x,y,'T',br+r[3]+1);
        uradi(x,y,'N',br+r[4]+1);
        uradi(x,y,'Q',br+r[5]+1);
    }

    if (cnt[n][m]==5000*5000)cnt[n][m]=-1;
    cout<<cnt[n][m];
    return 0;
}