#include "soccer.h"
#include <bits/stdc++.h>
using namespace std;
int biggest_stadium(int n, std::vector<std::vector<int>> F)
{
vector<vector<bool>> vis(n, vector<bool>(n, 0));
function<void(int, int)> dfs = [&](int i, int j){
vis[i][j] = 1;
if(i > 0 && !vis[i-1][j] && !F[i-1][j]) dfs(i-1, j);
if(j > 0 && !vis[i][j-1]&& !F[i][j-1]) dfs(i, j-1);
if(i < n-1 && !vis[i+1][j]&& !F[i+1][j]) dfs(i+1, j);
if(j < n-1 && !vis[i][j+1]&& !F[i][j+1]) dfs(i, j+1);
return;
};
int i0 = -1;
int j0 = -1;
int sol = 0;
for(int i = 0; i<n; i++){
for(int j = 0; j<n; j++){
if(!F[i][j]){
sol++;
if(i0 == -1){
i0 = i; j0 = j;
dfs(i0, j0);
}
else{
if(!vis[i][j]) return 0;
}
}
}
}
vector<vector<int>> pref1(n, vector<int>(n));
vector<vector<int>> pref2(n, vector<int>(n));
for(int i = 0; i<n; i++){
pref1[i][0] = F[i][0];
pref2[0][i] = F[0][i];
}
for(int i = 0; i<n; i++){
for(int j = 1; j<n; j++){
pref1[i][j] = pref1[i][j-1]+F[i][j];
pref2[j][i] = pref2[j-1][i]+F[j][i];
}
}
auto q1 = [&pref1](int i, int ll, int rr)->int{
if(ll>rr) swap(ll, rr);
return pref1[i][rr]-(ll ? pref1[i][ll-1] : 0);
};
auto q2 = [&pref2](int i, int ll, int rr)->int{
if(ll>rr) swap(ll, rr);
return pref2[rr][i]-(ll ? pref2[ll-1][i] : 0);
};
int i1 = -1;
for(int i = n-1; i>=0; i--){
for(int j = 0; j<n; j++){
if(!F[i][j]){
i1 = i;
break;
}
}
if(i1 != -1) break;
}
vector<int> l(n, -1);
vector<int> r(n, -1);
for(int i = i0; i<=i1; i++){
for(int j = 0; j<n; j++){
if(!F[i][j]) l[i] = j;
}
for(int j = n-1; j>=0; j--){
if(!F[i][j]) r[i] = j;
}
assert(l[i] != -1);
if(q1(i, l[i], r[i]) != 0) return 0;
}
for(int i = 0; i<2*n; i++){
for(int j =i+1; j<2*n; j++){
int ii0 = i/2;
int jj0 = (i&1 ? r[ii0] : l[ii0]);
int ii1 = j/2;
int jj1 = (j&1 ? r[ii1] : l[ii1]);
//condizione 1: ii0, jj0 --> ii1, jj0 --> ii1, jj1
int v1 = q2(jj0, ii0, ii1) + q1(ii1, jj0, jj1);
//condizone 2: ii0, jj0 --> ii0, jj1 --> ii1, jj1
int v2 = q1(ii0, jj0, jj1) + q2(jj1, ii0, ii1);
if(v1 != 0 && v2 != 0) return 0;
}
}
return sol;
}
