// time_limit/iterative_closure_random.cpp
#include "soccer.h"
#include <iostream>
int n;
std::vector<std::vector<int>> c;
std::vector<std::vector<int>> pre;
std::vector<std::vector<int>> st;
int sum(int a, int b, int x, int y)
{
if (a > x)
std::swap(a, x);
if (b > y)
std::swap(b, y);
return pre[x][y] - (b ? pre[x][b - 1] : 0) - (a ? pre[a - 1][y] : 0) + (a && b ? pre[a - 1][b - 1] : 0);
}
bool connected(int a, int b, int x, int y)
{
return sum(a, b, x, b) + sum(x, b, x, y) == 0 || sum(a, b, a, y) + sum(a, y, x, y) == 0;
}
std::vector<std::pair<int, int>> curr;
std::vector<std::pair<int, int>> vis;
int mx = 0;
void dfs(int x, int y)
{
if (c[x][y] || st[x][y])
return;
vis.push_back({x, y});
st[x][y] = 1;
bool ok = true;
for (auto i : curr)
{
ok &= connected(i.first, i.second, x, y);
}
if (ok)
{
curr.push_back({x, y});
}
else
{
return;
}
mx = std::max(mx, (int)curr.size());
if (x > 0)
dfs(x - 1, y);
if (y > 0)
dfs(x, y - 1);
if (y + 1 < n)
dfs(x, y + 1);
if (x + 1 < n)
dfs(x + 1, y);
}
int biggest_stadium(int N, std::vector<std::vector<int>> C)
{
n = N;
c = C;
pre.assign(n, std::vector<int>(n, 0));
st.assign(n, std::vector<int>(n, 0));
std::vector<std::pair<int, int>> lst;
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < n; ++j)
{
if (!c[i][j])
{
lst.push_back({i, j});
}
pre[i][j] = c[i][j];
if (i)
pre[i][j] += pre[i - 1][j];
if (j)
pre[i][j] += pre[i][j - 1];
if (i && j)
pre[i][j] -= pre[i - 1][j - 1];
}
}
double start = clock();
while (double(clock() - start) / CLOCKS_PER_SEC < 3.0)
{
std::pair<int, int> elem = lst[rand() % lst.size()];
curr.clear();
vis.clear();
dfs(elem.first, elem.second);
for (auto [x, y] : vis)
{
st[x][y] = 0;
}
}
return mx;
}
