#include <cstdio> #include <iostream> #include <vector> #include <map> #include <set> #include <string> #include <cstring> #include <sstream> #include <algorithm> #include <functional> #include <queue> #include <stack> #include <cmath> #include <iomanip> using namespace std; #define FOR(i,a,b) for(int i=(a);i<(b);++i) #define REP(i,n) FOR(i,0,n) #define CLR(a) memset((a), 0 ,sizeof(a)) #define MCLR(a) memset((a), -1 ,sizeof(a)) int dx[4] = { 1,-1, 0, 0}; int dy[4] = { 0, 0, 1,-1}; const int Max = 21; int w,h; char c[Max][Max]; bool f[Max][Max]; typedef pair<int,int> P; char mark[2] = {'a','b'}; int bfs(int i,int j) { if(i < 0 || j < 0 || i >= h || j >= w || f[i][j])return 0; queue<P> q; q.push( P(i,j) ); while(!q.empty()) { P now = q.front();q.pop(); int x = now.first,y = now.second; f[x][y] = true; if(c[x][y] == mark[1]) { return abs(x-i)+abs(y-j)-1; } for(int k = 0;k < 4;k++) { int tx = now.first+dx[k],ty = now.second+dy[k]; if((tx >= 0 && ty >= 0 && tx < h && ty < w && !f[tx][ty])) { q.push(P(tx,ty)); } } } } int dfs(int i,int j,char ma) { if(i < 0 || j < 0 || i >= h || j >= w || f[i][j])return 0; f[i][j] = true; if(c[i][j] == '#')return 0; if(c[i][j] == '.') { for(int k = 0;k < 4;k++) { int tx = i+dx[k];int ty = j+dy[k]; dfs(tx,ty,ma); } c[i][j] = ma; return 1; } return 0; } void cast(char ma) { for(int i = 0;i < h;i++) for(int j = 0;j < w;j++) { if(dfs(i,j,ma))return; } } int main() { cin >> w >> h; for(int i = 0;i < h;i++) for(int j = 0;j < w;j++) cin >> c[i][j]; for(int i = 0;i < 2;i++) { CLR(f); cast(mark[i]); } int anser = 99999999; for(int i = 0;i < h;i++) for(int j = 0;j < w;j++) { CLR(f); if(c[i][j] == mark[0]) { anser = min(bfs(i,j),anser); } } cout << anser << endl; return 0; }