#include <iostream> #include <fstream> #include <queue> using namespace std; const int NMAX = 1005; int a[NMAX][NMAX]; int d[NMAX][NMAX]; bool accesibil[NMAX][NMAX]; int dx[] = {-1, 0, 1, 0}; int dy[] = {0, 1, 0, -1}; int n, m; queue <pair <int, int> > q; void bfs() { while(!q.empty()) { pair <int, int> p =q.front(); q.pop(); int x = p.first; int y = p.second; for(int i = 0; i < 4; i++) { int nx = x + dx[i]; int ny = y + dy[i]; if(d[nx][ny] == -1) { d[nx][ny] = d[x][y] + 1; q.push({nx, ny}); } } } } bool exista_drum(int dist, pair<int, int> xs, pair <int, int> xf) { if(d[xs.first][xs.second] < dist) return false; for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) { accesibil[i][j] = true; if(d[i][j] < dist) accesibil[i][j] = false; } queue <pair <int, int> > q2; q2.push(xs); while(!q2.empty()) { pair <int, int> p = q2.front(); q2.pop(); for(int i = 0; i < 4; i++) { int x = p.first + dx[i]; int y = p.second + dy[i]; if(accesibil[x][y]) { if(x == xf.first && y == xf.second) return true; q2.push({x, y}); accesibil[x][y] = false; } } } return false; } int caut_bin(pair <int, int> xs, pair <int, int> xf) { int st, dr; st = 0; dr = n * m; int rasp = -1; while(st <= dr) { int mij = (st + dr) / 2; if(exista_drum(mij, xs, xf)) { rasp = mij; st = mij + 1; }else dr = mij - 1; } return rasp; } int main() { ifstream fin("barbar.in"); ofstream fout("barbar.out"); fin >> n >> m; for(int i = 0; i <= n + 1; i++) d[i][0] = d[i][m + 1] = -2; for(int i = 0; i <= m + 1; i++) d[0][i] = d[n + 1][i] = -2; int xs, ys, xf, yf; xs = ys = xf = yf = 0; for(int i = 1; i <= n; i++) { string s; fin >> s; for(int j = 1; j <= m; j++) { if(s[j - 1] == '.') a[i][j] = -1; else if(s[j - 1] == '*') a[i][j] = -2