#include <iostream>
#include <queue>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
int N;
bool isMove = false;
struct con{
int r;
int c;
int ct;
int chk;
};
int rl[8] = {0, 0, 1, -1, 1, 1, -1, -1};
int ud[8] = {1, -1, 0, 0, 1, -1, 1, -1};
vector<vector<int>> mat;
vector<vector<int>> paddler;
bool visited[52][52][2];
//1 -> vertical
//0 -> hortizental
bool isRotate(int row, int col){
bool isTree = true;
for (int i = 0; i < 8; i++)
{
if (mat[row + ud[i]][col + rl[i]] == 1)
{
isTree = false;
break;
}
}
return isTree;
}
int main(){
ios::sync_with_stdio(false);
cin >> N;
mat.resize(N + 2, vector<int>(N + 2, 1));
paddler.resize(N + 2, vector<int>(N + 2, 0));
vector<con> B;
vector<con> E;
string in;
for (int i = 1; i <= N; i++){
cin >> in;
for (int j = 0; j < in.length(); j++){
if (in[j] == '1') mat[i][j + 1] = 1;
else if (in[j] == 'B'){
mat[i][j + 1] = 0;
B.push_back({i, j + 1, 0, 0});
}
else if (in[j] == 'E'){
mat[i][j + 1] = 0;
E.push_back({i, j + 1, 0, 0});
}
else mat[i][j + 1] = 0;
}
}
queue<con> q;
if(E[0].r == E[1].r && E[1].r == E[2].r
&& E[0].c + 1 == E[1].c && E[1].c + 1 == E[2].c) E[1].chk = 0;
else if(E[0].c == E[1].c && E[1].c == E[2].c
&& E[0].r + 1 == E[1].r && E[1].r + 1 == E[2].r) E[1].chk = 1;
else {
printf("0");
return 0;
}
if(B[0].r == B[1].r && B[1].r == B[2].r
&& B[0].c + 1 == B[1].c && B[1].c + 1 == B[2].c) q.push(B[1]);
else if(B[0].c == B[1].c && B[1].c == B[2].c
&& B[0].r + 1 == B[1].r && B[1].r + 1 == B[2].r) {
B[1].chk = 1;
q.push({B[1].r, B[1].c, 0, B[1].chk});
}
else{
printf("0");
return 0;
}
visited[B[1].r][B[1].c][B[1].chk] = true;
paddler[B[1].r][B[1].c] = B[1].chk;
if (isRotate(B[1].r, B[1].c)){
q.push({B[1].r, B[1].c, B[1].ct + 1, 1 - B[1].chk});
visited[B[1].r][B[1].c][1- B[1].chk];
}
while(q.size()){
int row = q.front().r;
int col = q.front().c;
int cnt = q.front().ct;
int chk = q.front().chk;
cout << row << " " << col << " " << cnt << " " << chk << endl;
if(row == E[1].r && col == E[1].c && chk == E[1].chk){
printf("%d", cnt);
isMove = true;
break;
}
for(int i = 0; i < 4; i++){
int _row = row + ud[i];
int _col = col + rl[i];
if(mat[_row][_col] == 1) continue;
else if(chk == 1){
if(mat[_row + 1][_col] == 1 || mat[_row - 1][_col] == 1) continue;
if(visited[_row][_col][chk]) continue;
q.push({_row, _col, cnt + 1, chk});
visited[_row][_col][chk] = true;
if(isRotate(_row, _col) && !visited[_row][_col][1 - chk]){
q.push({_row, _col, cnt + 2, 1 - chk});
visited[_row][_col][1 - chk] = true;
}
}
else if(chk == 0){
if(mat[_row][_col + 1] == 1 || mat[_row][_col - 1] == 1) continue;
if(visited[_row][_col][chk]) continue;
q.push({_row, _col, cnt + 1, chk});
visited[_row][_col][chk] = true;
if(isRotate(_row, _col) && !visited[_row][_col][1 - chk]){
q.push({_row, _col, cnt + 2, 1 - chk});
visited[_row][_col][1 - chk] = true;
}
}
}
q.pop();
}
if(!isMove) cout << 0;
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8cXVldWU+CiNpbmNsdWRlIDx2ZWN0b3I+CiNpbmNsdWRlIDxzdHJpbmc+CiNpbmNsdWRlIDxhbGdvcml0aG0+Cgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKaW50IE47CmJvb2wgaXNNb3ZlID0gZmFsc2U7CgpzdHJ1Y3QgY29uewogICAgaW50IHI7CiAgICBpbnQgYzsKICAgIGludCBjdDsKICAgIGludCBjaGs7Cn07CgppbnQgcmxbOF0gPSB7MCwgMCwgMSwgLTEsIDEsIDEsIC0xLCAtMX07CmludCB1ZFs4XSA9IHsxLCAtMSwgMCwgMCwgMSwgLTEsIDEsIC0xfTsKCnZlY3Rvcjx2ZWN0b3I8aW50Pj4gbWF0Owp2ZWN0b3I8dmVjdG9yPGludD4+IHBhZGRsZXI7Cgpib29sIHZpc2l0ZWRbNTJdWzUyXVsyXTsKCiAgICAvLzEgLT4gdmVydGljYWwKICAgIC8vMCAtPiBob3J0aXplbnRhbAogICAgCmJvb2wgaXNSb3RhdGUoaW50IHJvdywgaW50IGNvbCl7CiAgICBib29sIGlzVHJlZSA9IHRydWU7CiAgICBmb3IgKGludCBpID0gMDsgaSA8IDg7IGkrKykKICAgIHsKICAgICAgICBpZiAobWF0W3JvdyArIHVkW2ldXVtjb2wgKyBybFtpXV0gPT0gMSkKICAgICAgICB7CiAgICAgICAgICAgIGlzVHJlZSA9IGZhbHNlOwogICAgICAgICAgICBicmVhazsKICAgICAgICB9CiAgICB9CiAgICByZXR1cm4gaXNUcmVlOwp9CgppbnQgbWFpbigpewogICAgaW9zOjpzeW5jX3dpdGhfc3RkaW8oZmFsc2UpOwogICAgY2luID4+IE47CiAgICBtYXQucmVzaXplKE4gKyAyLCB2ZWN0b3I8aW50PihOICsgMiwgMSkpOwogICAgcGFkZGxlci5yZXNpemUoTiArIDIsIHZlY3RvcjxpbnQ+KE4gKyAyLCAwKSk7CgogICAgdmVjdG9yPGNvbj4gQjsKICAgIHZlY3Rvcjxjb24+IEU7CgogICAgc3RyaW5nIGluOwoKICAgIGZvciAoaW50IGkgPSAxOyBpIDw9IE47IGkrKyl7CiAgICAgICAgY2luID4+IGluOwogICAgICAgIGZvciAoaW50IGogPSAwOyBqIDwgaW4ubGVuZ3RoKCk7IGorKyl7CiAgICAgICAgICAgIGlmIChpbltqXSA9PSAnMScpIG1hdFtpXVtqICsgMV0gPSAxOwogICAgICAgICAgICBlbHNlIGlmIChpbltqXSA9PSAnQicpewogICAgICAgICAgICAgICAgbWF0W2ldW2ogKyAxXSA9IDA7CiAgICAgICAgICAgICAgICBCLnB1c2hfYmFjayh7aSwgaiArIDEsIDAsIDB9KTsKICAgICAgICAgICAgfQogICAgICAgICAgICBlbHNlIGlmIChpbltqXSA9PSAnRScpewogICAgICAgICAgICAgICAgbWF0W2ldW2ogKyAxXSA9IDA7CiAgICAgICAgICAgICAgICBFLnB1c2hfYmFjayh7aSwgaiArIDEsIDAsIDB9KTsKICAgICAgICAgICAgfQogICAgICAgICAgICBlbHNlIG1hdFtpXVtqICsgMV0gPSAwOyAKICAgICAgICB9CiAgICB9CgogICAgcXVldWU8Y29uPiBxOwoKICAgIGlmKEVbMF0uciA9PSBFWzFdLnIgJiYgRVsxXS5yID09IEVbMl0ucgogICAgJiYgRVswXS5jICsgMSA9PSBFWzFdLmMgJiYgRVsxXS5jICsgMSA9PSBFWzJdLmMpIEVbMV0uY2hrID0gMDsKICAgIGVsc2UgaWYoRVswXS5jID09IEVbMV0uYyAmJiBFWzFdLmMgPT0gRVsyXS5jCiAgICAmJiBFWzBdLnIgKyAxID09IEVbMV0uciAmJiBFWzFdLnIgKyAxID09IEVbMl0ucikgRVsxXS5jaGsgPSAxOwogICAgZWxzZSB7CiAgICAgICAgcHJpbnRmKCIwIik7CiAgICAgICAgcmV0dXJuIDA7CiAgICB9CgogICAgaWYoQlswXS5yID09IEJbMV0uciAmJiBCWzFdLnIgPT0gQlsyXS5yCiAgICAmJiBCWzBdLmMgKyAxID09IEJbMV0uYyAmJiBCWzFdLmMgKyAxID09IEJbMl0uYykgcS5wdXNoKEJbMV0pOwogICAgZWxzZSBpZihCWzBdLmMgPT0gQlsxXS5jICYmIEJbMV0uYyA9PSBCWzJdLmMKICAgICYmIEJbMF0uciArIDEgPT0gQlsxXS5yICYmIEJbMV0uciArIDEgPT0gQlsyXS5yKSB7CiAgICAgICAgQlsxXS5jaGsgPSAxOwogICAgICAgIHEucHVzaCh7QlsxXS5yLCBCWzFdLmMsIDAsIEJbMV0uY2hrfSk7CiAgICB9CiAgICBlbHNlewogICAgICAgIHByaW50ZigiMCIpOwogICAgICAgIHJldHVybiAwOwogICAgfQogICAgdmlzaXRlZFtCWzFdLnJdW0JbMV0uY11bQlsxXS5jaGtdID0gdHJ1ZTsKICAgIHBhZGRsZXJbQlsxXS5yXVtCWzFdLmNdID0gQlsxXS5jaGs7CiAgICBpZiAoaXNSb3RhdGUoQlsxXS5yLCBCWzFdLmMpKXsKICAgICAgICBxLnB1c2goe0JbMV0uciwgQlsxXS5jLCBCWzFdLmN0ICsgMSwgMSAtIEJbMV0uY2hrfSk7CiAgICAgICAgdmlzaXRlZFtCWzFdLnJdW0JbMV0uY11bMS0gQlsxXS5jaGtdOwogICAgfQoKICAgIHdoaWxlKHEuc2l6ZSgpKXsKICAgICAgICBpbnQgcm93ID0gcS5mcm9udCgpLnI7CiAgICAgICAgaW50IGNvbCA9IHEuZnJvbnQoKS5jOwogICAgICAgIGludCBjbnQgPSBxLmZyb250KCkuY3Q7CiAgICAgICAgaW50IGNoayA9IHEuZnJvbnQoKS5jaGs7CgogICAgICAgIGNvdXQgPDwgcm93IDw8ICIgIiA8PCBjb2wgPDwgIiAiIDw8IGNudCA8PCAiICIgPDwgY2hrIDw8IGVuZGw7CgogICAgICAgIGlmKHJvdyA9PSBFWzFdLnIgJiYgY29sID09IEVbMV0uYyAmJiBjaGsgPT0gRVsxXS5jaGspewogICAgICAgICAgICBwcmludGYoIiVkIiwgY250KTsKICAgICAgICAgICAgaXNNb3ZlID0gdHJ1ZTsKICAgICAgICAgICAgYnJlYWs7CiAgICAgICAgfQoKICAgICAgICBmb3IoaW50IGkgPSAwOyBpIDwgNDsgaSsrKXsKICAgICAgICAgICAgaW50IF9yb3cgPSByb3cgKyB1ZFtpXTsKICAgICAgICAgICAgaW50IF9jb2wgPSBjb2wgKyBybFtpXTsKCiAgICAgICAgICAgIGlmKG1hdFtfcm93XVtfY29sXSA9PSAxKSBjb250aW51ZTsKICAgICAgICAgICAgZWxzZSBpZihjaGsgPT0gMSl7CiAgICAgICAgICAgICAgICBpZihtYXRbX3JvdyArIDFdW19jb2xdID09IDEgfHwgbWF0W19yb3cgLSAxXVtfY29sXSA9PSAxKSBjb250aW51ZTsKICAgICAgICAgICAgICAgIGlmKHZpc2l0ZWRbX3Jvd11bX2NvbF1bY2hrXSkgY29udGludWU7CiAgICAgICAgICAgICAgICBxLnB1c2goe19yb3csIF9jb2wsIGNudCArIDEsIGNoa30pOwogICAgICAgICAgICAgICAgdmlzaXRlZFtfcm93XVtfY29sXVtjaGtdID0gdHJ1ZTsKICAgICAgICAgICAgICAgIGlmKGlzUm90YXRlKF9yb3csIF9jb2wpICYmICF2aXNpdGVkW19yb3ddW19jb2xdWzEgLSBjaGtdKXsKICAgICAgICAgICAgICAgICAgICBxLnB1c2goe19yb3csIF9jb2wsIGNudCArIDIsIDEgLSBjaGt9KTsKICAgICAgICAgICAgICAgICAgICB2aXNpdGVkW19yb3ddW19jb2xdWzEgLSBjaGtdID0gdHJ1ZTsKICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgfQogICAgICAgICAgICBlbHNlIGlmKGNoayA9PSAwKXsKICAgICAgICAgICAgICAgIGlmKG1hdFtfcm93XVtfY29sICsgMV0gPT0gMSB8fCBtYXRbX3Jvd11bX2NvbCAtIDFdID09IDEpIGNvbnRpbnVlOwogICAgICAgICAgICAgICAgaWYodmlzaXRlZFtfcm93XVtfY29sXVtjaGtdKSBjb250aW51ZTsKICAgICAgICAgICAgICAgIHEucHVzaCh7X3JvdywgX2NvbCwgY250ICsgMSwgY2hrfSk7CiAgICAgICAgICAgICAgICB2aXNpdGVkW19yb3ddW19jb2xdW2Noa10gPSB0cnVlOwogICAgICAgICAgICAgICAgaWYoaXNSb3RhdGUoX3JvdywgX2NvbCkgJiYgIXZpc2l0ZWRbX3Jvd11bX2NvbF1bMSAtIGNoa10pewogICAgICAgICAgICAgICAgICAgIHEucHVzaCh7X3JvdywgX2NvbCwgY250ICsgMiwgMSAtIGNoa30pOwogICAgICAgICAgICAgICAgICAgIHZpc2l0ZWRbX3Jvd11bX2NvbF1bMSAtIGNoa10gPSB0cnVlOwogICAgICAgICAgICAgICAgfQogICAgICAgICAgICB9CiAgICAgICAgfQogICAgICAgIHEucG9wKCk7CiAgICB9CgogICAgaWYoIWlzTW92ZSkgY291dCA8PCAwOwoKICAgIHJldHVybiAwOwp9