#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include //#include //#include //#include //#include using namespace std; //#define int long long typedef long long ll; typedef unsigned long long ul; typedef unsigned int ui; constexpr ll mod = 998244353; const ll INF = mod * mod; typedef pairP; #define stop char nyaa;cin>>nyaa; #define rep(i,n) for(int i=0;i=0;i--) #define Rep(i,sta,n) for(int i=sta;i=1;i--) #define Rep1(i,sta,n) for(int i=sta;i<=n;i++) #define all(v) (v).begin(),(v).end() typedef pair LP; typedef long double ld; typedef pair LDP; const ld eps = 1e-8; const ld pi = acosl(-1.0); ll mod_pow(ll x, ll n, ll m) { if (x >= m)x %= m; ll res = 1; while (n) { if (n & 1)res = res * x % m; x = x * x % m; n >>= 1; } return res; } struct uf { private: vector par, ran; public: uf(int n) { par.resize(n, 0); ran.resize(n, 0); rep(i, n) { par[i] = i; } } int find(int x) { if (par[x] == x)return x; else return par[x] = find(par[x]); } void unite(int x, int y) { x = find(x), y = find(y); if (x == y)return; if (ran[x] < ran[y]) { par[x] = y; } else { par[y] = x; if (ran[x] == ran[y])ran[x]++; } } bool same(int x, int y) { return find(x) == find(y); } }; int dx[8] = { 0,1,1,1,0,-1,-1,-1 }; int dy[8] = { 1,1,0,-1,-1,-1,0,1 }; char mp[1004][1004]; void solve() { int h, w; cin >> h >> w; rep(i, h + 4)rep(j, w + 4)mp[i][j] = '.'; rep1(i, h)rep1(j, w)cin >> mp[i+1][j+1]; rep(i, h + 4)rep(j, w + 4) { if (i == 0 || j == 0 || i == h + 3 || j == w + 3) { mp[i][j] = 'x'; } } h += 4; w += 4; uf u(h* w); rep(i, h)rep(j, w) { if (mp[i][j] != 'x')continue; rep(d, 8) { int nx = i + dx[d]; int ny = j + dy[d]; if (nx < 0 || ny < 0 || nx == h || ny == w)continue; if (mp[nx][ny] == 'x') { u.unite(i * w + j, nx * w + ny); } } } vector> fG(h* w); queue q; q.push(u.find(0)); vector> used(h,vector(w,false)); while (!q.empty()) { int fr = q.front(); q.pop(); int x = fr / w, y = fr%w; queue

que; rep(d, 8) { int nx = x + dx[d]; int ny = y + dy[d]; if (nx < 0 || ny < 0 || nx == h || ny == w)continue; if (used[nx][ny] || mp[nx][ny] == 'x')continue; que.push({ nx,ny }); used[nx][ny] = true; } vector tos; while (!que.empty()) { P p = que.front(); que.pop(); int cx = p.first, cy = p.second; rep(d, 8) { if (dx[d] == 0 || dy[d] == 0) { int nx = cx + dx[d]; int ny = cy + dy[d]; if (nx < 0 || ny < 0 || nx == h || ny == w)continue; if (mp[nx][ny] == 'x') { int tp = u.find(nx * w + ny); if (tp != fr)tos.push_back(tp); continue; } if (!used[nx][ny]) { used[nx][ny] = true; que.push({ nx, ny }); } } } } sort(all(tos)); tos.erase(unique(all(tos)),tos.end()); fG[fr] = tos; for (int id : tos)q.push(id); } vector cnt(h* w); rep(i, h)rep(j, w) { int p = u.find(i * w + j); cnt[p]++; } cnt[u.find(0)] = 0; function dfs = [&](int id)->P { P res = { 0,cnt[id] }; for (int to : fG[id]) { P nex = dfs(to); res.first += max(nex.first, nex.second); res.second += nex.first; } return res; }; P p = dfs(u.find(0)); int ans = max(p.first, p.second); cout << ans << "\n"; } signed main() { ios::sync_with_stdio(false); cin.tie(0); //cout << fixed << setprecision(15); //init_f(); //init(); //expr(); //int t; cin >> t; rep(i, t) solve(); return 0; }