#include "bits/stdc++.h" using namespace std; #ifdef _DEBUG #include "dump.hpp" #else #define dump(...) #endif //#define int long long #define rep(i,a,b) for(int i=(a);i<(b);i++) #define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--) #define all(c) begin(c),end(c) const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f; const int MOD = 1'000'000'007; template bool chmax(T &a, const T &b) { if (a < b) { a = b; return true; } return false; } template bool chmin(T &a, const T &b) { if (b < a) { a = b; return true; } return false; } using Weight = int; struct Edge { int s, d; Weight w; Edge() {}; Edge(int s, int d, Weight w) : s(s), d(d), w(w) {}; }; bool operator<(const Edge &e1, const Edge &e2) { return e1.w < e2.w; } bool operator>(const Edge &e1, const Edge &e2) { return e2 < e1; } inline ostream &operator<<(ostream &os, const Edge &e) { return (os << '(' << e.s << ", " << e.d << ", " << e.w << ')'); } using Edges = vector; using Graph = vector; using Array = vector; using Matrix = vector; void addArc(Graph &g, int s, int d, Weight w = 1) { g[s].emplace_back(s, d, w); } void addEdge(Graph &g, int a, int b, Weight w = 1) { addArc(g, a, b, w); addArc(g, b, a, w); } auto zeroOneBfs = [&](const Graph &g, int s, Array &dist) { int n = g.size(); deque dq = { s }; dist.assign(n, INF); dist[s] = 0; while (dq.size()) { int v = dq.front(); dq.pop_front(); for (auto &e : g[v]) { if (dist[e.d] == INF) { dist[e.d] = dist[v] + e.w; if (e.w == 0) dq.push_front(e.d); else dq.push_back(e.d); } } } }; signed main() { cin.tie(0); ios::sync_with_stdio(false); int W, H; cin >> W >> H; vector> C(H, vector(W)); rep(i, 0, H) rep(j, 0, W) { cin >> C[i][j]; } Graph g(H*W); static const int di[] = { 1,0,-1,0 }; static const int dj[] = { 0,1,0,-1 }; rep(i, 1, H - 1)rep(j, 1, W - 1) { rep(d, 0, 4) { int ni = i + di[d], nj = j + dj[d]; addArc(g, i*W + j, ni*W + nj, C[ni][nj] == '#'); } } rep(i, 0, H)rep(j, 0, W) { if (C[i][j] == '.') { Array dist; zeroOneBfs(g, i*W + j, dist); int ans = 0; rep(ni, 0, H)rep(nj, 0, W) { if (C[ni][nj] == '.') chmax(ans, dist[ni*W + nj]); } cout << ans << endl; return 0; } } return 0; }