[ABC351D] Grid and Magnet 连通块dfs 未解决
作者:
多米尼克領主的致意
,
2024-04-27 21:25:17
,
所有人可见
,
阅读 2
会T六个点 因为每次要memset st数组 因此会超时
#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
char g[N][N];
int n, m;
bool st[N][N];
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
int dfs(int x, int y)
{
// if(g[x][y] == '!')return 1;
int res = 1;
for(int i = 0;i < 4;i++)
{
int xx = x + dx[i], yy = y +dy[i];
if(xx >= 1 && xx <= n && yy >= 1 && yy <= m && g[xx][yy] != '#')
{
if(g[xx][yy] != '!')
{
g[xx][yy] = '#';
}
else
{
if(st[xx][yy])continue;
res += 1;
st[xx][yy] = true;
continue;
}
res += dfs(xx, yy);
}
}
return res;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
for(int i = 1;i <= n;i++)
{
for(int j = 1;j <= m;j++)
{
cin >> g[i][j];
}
}
for(int i = 1;i <= n;i++)
{
for(int j = 1;j <= m;j++)
{
if(g[i][j] == '#')
{
if(g[i][j + 1] != '#')
g[i][j + 1] = '!';
if(g[i + 1][j] != '#')
g[i + 1][j] = '!';
if(g[i - 1][j] != '#')
g[i - 1][j] = '!';
if(g[i][j - 1] != '#')
g[i][j - 1] = '!';
}
}
}
int ans = 0;
// memset(vis, 1, sizeof vis);
for(int i = 1;i <= n;i++)
{
for(int j = 1;j <= m;j++)
{
if(g[i][j] != '#' && g[i][j] != '!')
{
g[i][j] = '#';
ans = max(ans, dfs(i, j));
// bool st[N][N];
// memset(st, 0, sizeof st);
}
}
}
if(!ans)ans++;
cout << ans <<endl;
return 0;
}