条玄求关

https://www.luogu.com.cn/problem/CF1985H1

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e6 + 5;
ll t, n, m, mx, cnt;
ll a[N], v[N], sz[N];
ll ID(ll x, ll y) {return m * (x - 1) + y;}
ll dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1};
void dfs(ll x, ll y)
{
	v[ID(x, y)] = true;
	a[ID(x, y)] = cnt;
	sz[cnt]++;
	for (int i = 0; i < 4; i++)
	{
		ll xx = x + dx[i], yy = y + dy[i];
		if (xx < 1 or xx > n or yy < 1 or yy > m)
			continue;
		if (a[ID(xx, yy)] != -1 or v[ID(xx, yy)])
			continue;
		dfs(xx, yy);
	}
	return;
}
void solve()
{
	memset(a, 0, sizeof a);
	memset(v, 0, sizeof v);
	memset(sz, 0, sizeof sz);
	mx = -1, cnt = 0;
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			char ch;
			cin >> ch;
			a[ID(i, j)] = (ch == '#' ? -1 : 0);
		}
	}
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			if (!v[ID(i, j)] and a[ID(i, j)] == -1)
			{
				cnt++;
				dfs(i, j);
			}
	set <ll> st;
	ll k = 0;
	for (int i = 1; i <= n; i++)
	{
		st.clear();
		k = 0;
		for (int j = 1; j <= m; j++)
		{
			if (a[ID(i, j)])
				st.insert(a[ID(i, j)]);
			if (a[ID(i - 1, j)] and i > 1)
				st.insert(a[ID(i - 1, j)]);
			if (a[ID(i + 1, j)] and i < n)
				st.insert(a[ID(i + 1, j)]);
			if (!a[ID(i, j)])
				k++;
		}
		for (auto s : st)
			k += sz[s];
		mx = max(mx, k);
	}
	for (int j = 1; j <= m; j++)
	{
		st.clear();
		k = 0;
		for (int i = 1; i <= n; i++)
		{
			if (a[ID(i, j)])
				st.insert(a[ID(i, j)]);
			if (a[ID(i, j - 1)] and j > 1)
				st.insert(a[ID(i, j - 1)]);
			if (a[ID(i, j + 1)] and j < m)
				st.insert(a[ID(i, j + 1)]);
			if (!a[ID(i, j)])
				k++;
		}
		for (auto s : st)
			k += sz[s];
		mx = max(mx, k);
	}
	cout << mx << '\n';
	return;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> t;
	while (t--)
	{
		solve();
	}
	return 0;
}
/*
1
6 6
.#..#.
#..#..
.#...#
#.#.#.
.#.##.
###..#
*/