Vasilică vizitează cetățile medievale. Fiind curios, el încearcă să descopere pasajele secrete și ascunzătorile. Din nefericire, s-a rătăcit și a ajuns într-o sală din care nu poate ieși decât trecând printr-un labirint. Există o hartă a labirintului, o matrice de n linii și m coloane, un element din această matrice reprezentând o cameră. Deplasarea în labirint se poate face numai prin camerele adiacente pe orizontală și verticală. Intrările în labirint sunt notate cu A, ieșirile cu C, iar camerele zidite (inaccesibile) cu Z. Ieșirea din labirint se poate face din una din camerele C, în fiecare astfel de cameră existând câte un elicopter încuiat. Toate elicopterele se deschid cu aceeași cheie, câte un exemplar al cheii aflându-se în camerele B. Trecerea în altă cameră va dura 1 unitate de timp. Pentru a ieși din labirint Vasilică intră pe una din intrările notate cu A, ia cheia dintr-o cameră B și iese din labirint printr-o cameră C. El va intra în camera A la timpul 1. Camerele de tip A pot fi situate oriunde pe hartă. În drumul de la o cameră de tip A către o cameră de tip B se poate trece printr-o cameră de tip C fără a se ieși din labirint.

Cerința

Ajutați-l pe Vasilică să iasă cât mai repede din labirint.

Date de intrare

Fișierul de intrare labirint.in conține pe prima linie numărul n de linii şi numărul m de coloane ale hărții, iar pe următoarele n linii, câte m caractere, reprezentând elementele acesteia. Caracterele pot fi _, A, B, C, Z cu semnificația din text. _ reprezintă o cameră fără restricții (liberă).

Date de ieșire

Pe prima linie a fişierului de ieşire labirint.out se va scrie numărul ce reprezintă timpul cel mai scurt în care Vasilică poate să iasă din labirint.

Restricții și precizări

• 1 ≤ n, m ≤ 1000
• întotdeauna există un drum de ieșire
• operația de luare a cheii sau a elicopterului dintr-o cameră nu consumă timp

Exemplu

labirint.in

5 6
ZA____
A__Z__
A_C__B
C___Z_
___B_Z

labirint.out

9

Explicație

Timpul cel mai scurt în care Vasilică poate să iasă din labirint este de 9 unități și avem două variante: plecăm din A(3,1) la timpul 1 și ajungem în B(3,6) sau în B(5,4) la timpul 6 (luăm cheia) și ieșim prin C(3,3) la timpul 9.

#include <bits/stdc++.h>

using namespace std;

# define inf 1000000001

ifstream cin("labirint.in");
ofstream cout("labirint.out");

char mat[1001][1001], ch;
int n, m, a[1001][1001];
queue<pair<int, int>> Q;

bool inmat(int i, int j){
    return i >= 1 && j >= 1 && i <= n && j <= m;
}

int di[]={0,0,-1,1};
int dj[]={-1,1,0,0};

void lee(){
    while(!Q.empty()){
        pair<int, int> p;
        p = Q.front();
        for(int d = 0; d <= 3; ++d){
            int inou = p.first + di[d];
            int jnou = p.second + dj[d];
            if(inmat(inou, jnou) && a[inou][jnou] != -1 && a[inou][jnou] > a[p.first][p.second] + 1)
                a[inou][jnou] = a[p.first][p.second] + 1, Q.push(make_pair(inou, jnou));
        }
        Q.pop();
    }
}

int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j)
            cin >> ch, mat[i][j] = ch;
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j){
            if(mat[i][j] == 'Z')
                a[i][j] = -1;
            else if(mat[i][j] == 'A')
                Q.push(make_pair(i, j));
            else
                a[i][j] = inf;
        }
    lee();
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j){
            if(mat[i][j] == 'Z')
                a[i][j] = -1;
            else if(mat[i][j] == 'B')
                Q.push(make_pair(i, j));
            else
                a[i][j] = inf;
        }
    lee();
    int mini = 1000000000;
    for(int i = 1; i <= n; ++i)
    for(int j = 1; j <= m; ++j){
        if(mat[i][j] == 'C' && a[i][j] < mini)
            mini = a[i][j];
    }
    cout << mini + 1;
    return 0;
}