// 深さ優先探索 枡目マップ探索
#include <bits/stdc++.h>
using namespace std;
#define int long long
using P = pair<int, int>;
constexpr array<int, 4> dx = {1, 0, -1, 0};
constexpr array<int, 4> dy = {0, 1, 0, -1};
constexpr int INF = 1010101010;
constexpr int MOD = 1000000000 + 7;
// constexpr int MOD = 998244353;
template <class T>
bool chmax(T &a, const T &b)
{
    if (a < b)
    {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T &a, const T &b)
{
    if (b < a)
    {
        a = b;
        return 1;
    }
    return 0;
}
constexpr int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
constexpr int fact(int n) { return n > 1 ? n * fact(n - 1) % MOD : 1; }
int modinv(int a)
{
    int b = MOD, u = 1, v = 0;
    while (b)
    {
        int t = a / b;
        a -= t * b;
        swap(a, b);
        u -= t * v;
        swap(u, v);
    }
    u %= MOD;
    if (u < 0)
        u += MOD;
    return u;
}
constexpr int modpow(int a, int n)
{
    int rtn = 1;
    while (n > 0)
    {
        if (n & 1)
            rtn = rtn * a % MOD;
        a = a * a % MOD;
        n >>= 1;
    }
    return rtn;
}

constexpr char PASS = '.', WALL = '#';
// 升目マップを探索する
class squareMap
{
private:
    vector<string> _map;
    int _h, _w;
    pair<int, int> _start{INF, INF}, _goal{INF, INF};
    // スタートから各升の距離を記録 その升をすでに探索したかどうかも記録 INFは調べていないことを意味する
    vector<vector<int>> _distance;
    bool inMap(pair<int, int> p) const { return 0 <= p.first && p.first < _h && 0 <= p.second && p.second < _w; }

public:
    // コンストラクタ 引数mapはマスの種類を文字で表した文字列ベクトルを
    squareMap(vector<string> map);
    ~squareMap();
    bool setStart(char letter, queue<pair<int, int>> &q);
    void setSquare(int y, int x, char square = PASS) { _map[y][x] = square; }
    char getSquare(int y, int x, char square = PASS) const { return _map[y][x]; }
    int search();
    int getMaxDist() const;
    void resetDist()
    {
        _distance.resize(_h);
        for (auto &&di : _distance)
            di.assign(_w, INF);
    }

    // キュー使用幅優先探索で，スタートからゴールにたどり着けるかどうか探索する．
};

squareMap::squareMap(vector<string> map) : _map(map)
{
    _h = _map.size();
    _w = _map.size() > 0 ? _map[0].size() : 0;
    _distance.resize(_h);
    for (auto &&di : _distance)
    {
        di.assign(_w, INF);
    }
}

squareMap::~squareMap()
{
}

bool squareMap::setStart(char letter, queue<pair<int, int>> &q)
{
    // STARTを探す
    for (int i = 0; i < _h; i++)
    {
        for (int j = 0; j < _w; j++)
        {
            if (letter == _map[i][j])
            {
                q.push({i, j});
                _distance[i][j] = 0;
            }
        }
    }
    return true;
}

int squareMap::search()
{
    // 調べる升を記録するキュー
    queue<pair<int, int>> destination;

    // 最初にスタートを探索した
    setStart('#', destination);

    // 全ての升を調べ終わるか，ゴールが見つかるまで調べる
    while (!destination.empty())
    {
        // キューから調べる升を取り出す
        pair<int, int> p = destination.front();
        destination.pop();
        // 調べる升がゴールなら終わり
        if (p == _goal)
            break;

        // 次に調べる升の上下左右を調べる
        for (int i = 0; i < dx.size(); i++)
        {
            // np: 次に調べる升の上下左右の升
            pair<int, int> np = {p.first + dy[i], p.second + dx[i]};
            // npが枡目内に存在する，npが壁ではないかつnpをすでに探索していないか確認
            if (inMap(np) && _map[np.first][np.second] != WALL && _distance[np.first][np.second] == INF)
            {
                // npを今後調べる升としてスタックに積む
                destination.push(np);
                // npまでの距離を記録する
                _distance[np.first][np.second] = _distance[p.first][p.second] + 1;
                setSquare(np.first, np.second, WALL);
            }
        }
    }
    // ゴールまでの距離を返す
    return getMaxDist();
}

int squareMap::getMaxDist() const
{
    int max_dist = 0;
    for (int i = 0; i < _h; i++)
        for (int j = 0; j < _w; j++)
            if (_distance[i][j] != INF)
            {
                chmax(max_dist, _distance[i][j]);
            }
    return max_dist;
}

signed main()
{
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout << setprecision(10);

    // 入力例
    // 5 5
    // ##.##
    // s..##
    // #.###
    // #....
    // #.##g
    int h, w;
    cin >> h >> w;
    vector<string> map0(h);
    for (auto &&row_map : map0)
        cin >> row_map;

    squareMap sm(map0);
    cout << sm.search() << endl;
}


Measured memory_bytes: 26548