ABC351D
  • 板块学术版
  • 楼主Mr_Biantainne
  • 当前回复3
  • 已保存回复3
  • 发布时间2024/4/27 21:42
  • 上次更新2024/4/28 10:45:11
查看原帖
ABC351D
545601
Mr_Biantainne楼主2024/4/27 21:42

错两个点,调不出来

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll h, w, rec, tot, ans, f[1005][1005], dx[5] = {0, 0, 0, 1, -1}, dy[5] = {0, 1, -1, 0, 0};
char c[1005][1005];
bool vis[1005][1005], vis2[1005][1005], vis3[1005][1005];
bool check(ll x, ll y)
{
	if (c[x][y - 1] == '#' || c[x][y + 1] == '#' || c[x - 1][y] == '#' || c[x + 1][y] == '#') return 1;
	return 0;
}
void dfs(ll x, ll y)
{
	rec++;
	vis[x][y] = 1;
	for (ll i = 1; i <= 4; i++)
	{
		ll nx = x + dx[i], ny = y + dy[i];
		if (f[nx][ny]) vis3[nx][ny] = 1;
		if (nx < 1 || nx > h || ny < 1 || ny > w || vis[nx][ny] || f[nx][ny]) continue;
		dfs(nx, ny);
	}
}
void dfs2(ll x, ll y)
{
	vis2[x][y] = 1;
	f[x][y] = rec;
	for (ll i = 1; i <= 4; i++)
	{
		ll nx = x + dx[i], ny = y + dy[i];
		tot += vis3[nx][ny];
		vis3[nx][ny] = 0;
		if (nx < 1 || nx > h || ny < 1 || ny > w || vis2[nx][ny] || f[nx][ny]) continue;
		dfs2(nx, ny);
	}
}
int main()
{
	cin >> h >> w;
	for (ll i = 1; i <= h; i++) for (ll j = 1; j <= w; j++) cin >> c[i][j];
	for (ll i = 1; i <= h; i++) for (ll j = 1; j <= w; j++)
	{
		if (c[i][j] == '#') f[i][j] = -1;
		else if (check(i, j)) f[i][j] = 1;
	}
	for (ll i = 1; i <= h; i++) for (ll j = 1; j <= w; j++)
	{
		if (!f[i][j])
		{
			rec = tot = 0;
			dfs(i, j);
			dfs2(i, j);
		}
		ans = max(ans, f[i][j] + tot);
	}
	cout << ans;
}

真是太丢人了

2024/4/27 21:42
加载中...