ABC D 求调
  • 板块学术版
  • 楼主No_Rest
  • 当前回复8
  • 已保存回复8
  • 发布时间2024/4/27 21:45
  • 上次更新2024/4/28 11:17:29
查看原帖
ABC D 求调
550821
No_Rest楼主2024/4/27 21:45

rt,WA x4

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn = 1e3 + 5;
const ll dx[5] = {0, 1, 0, -1};
const ll dy[5] = {1, 0, -1, 0};
ll read(){
	char ch;
	ll f = 0, r = 0;
	ch = getchar();
	while(ch > '9' || ch < '0') f |= ch == '-', ch = getchar();
	while(ch <= '9' && ch >= '0') r = (r << 3) + (r << 1) + (ch ^ 48), ch = getchar();
	return f ? -r : r;
}
ll n = read(), m = read(), ans, a[maxn][maxn], vis[maxn][maxn];
char ch;
queue < pair <ll, ll> > q, q1;
int main(){
	for(ll i = 1; i <= n; ++i)
		for(ll j = 1; j <= m; ++j){
			cin >> ch;
			if(ch == '#') a[i][j] = 2, a[i - 1][j] = a[i][j - 1] = a[i + 1][j] = a[i][j + 1] = 1;
		}
	for(ll i = 1; i <= n; ++i)
		for(ll j = 1; j <= n; ++j)
			if(a[i][j] == 1) ans = max(ans, 1ll);
			else if(!vis[i][j] && !a[i][j]){
				ll siz = 0;
				// cout << i << ' ' << j << ": \n";
				while(q1.size()) q1.pop();
				while(q.size()) q.pop();
				q.push({i, j});
				while(q.size()){
					auto u = q.front(); q.pop();
					vis[u.first][u.second] = 1, siz++;
					if(a[u.first][u.second] == 1){
						q1.push(u);
						continue;
					}
					// cout << u.first << ' ' << u.second << '\n';
					// system("pause");
					for(ll i = 0; i < 4; ++i){
						ll nx = u.first + dx[i], ny = u.second + dy[i];
						if(nx && ny && nx <= n && ny <= m && a[nx][ny] != 2 && !vis[nx][ny]) q.push({nx, ny}), vis[nx][ny] = 1;
					}
				}
				while(q1.size()){
					vis[q1.front().first][q1.front().second] = 0;
					q1.pop();
				}
				ans = max(ans, siz);
			}
	printf("%lld", ans);
	return 0;
}
2024/4/27 21:45
加载中...