#include "soccer.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define all(x) x.begin(),x.end()
#define ll long long
#define ff first
#define ss second
const int N = 200005;
int arr[4][2]={
{0, 1},
{0, -1},
{1, 0},
{-1, 0}
};
int biggest_stadium(int n, std::vector<std::vector<int>> a)
{
vector<vector<int>> U(n, vector<int>(n));
vector<vector<int>> L(n, vector<int>(n));
for(int i = 0; i < n; ++i){
for(int j = 0; j < n; ++j){
if(i == 0){
if(a[i][j] == 1) U[i][j] = i;
else U[i][j] = -1;
}else{
if(a[i][j] == 1){
if(a[i - 1][j] == 1) U[i][j] = U[i - 1][j];
else U[i][j] = i;
}else{
U[i][j] = -1;
}
}
if(j == 0){
if(a[i][j] == 1) L[i][j] = j;
else U[i][j] = -1;
}else{
if(a[i][j] == 1){
if(a[i][j - 1] == 1) L[i][j] = L[i][j - 1];
else L[i][j] = j;
}else{
L[i][j] = -1;
}
}
}
}
queue<pair<int, int>> q;
vector<vector<bool>> vis(n, vector<bool>(n));
for(int i = 0; i < n; ++i){
for(int j = 0; j < n; ++j){
if(a[i][j] == 0){
q.push({i, j});
vis[i][j] = 1;
break;
}
}
if(q.size()) break;
}
int sz = 0;
while(!q.empty()){
int x = q.front().ff;
int y = q.front().ss;
q.pop();
for(int i = 0; i < 4; ++i){
int nx = x + arr[i][0];
int ny = y + arr[i][1];
if(nx >= 0 && ny >= 0 && nx < n && ny < n && !vis[nx][ny] && a[nx][ny] == 0){
vis[nx][ny] = 1;
q.push({nx, ny});
}
}
}
for(int i = 0; i < n; ++i){
for(int j = 0; j < n; ++j){
if(a[i][j] == 0 && vis[i][j] == 0){
return false;
}
if(a[i][j] == 1) continue;
++sz;
if(i > 0){
if(a[i - 1][j] == 1){
int pos = U[i - 1][j];
if(pos > 0 && a[pos - 1][j] == 0){
return false;
}
}
}
if(j > 0){
if(a[i][j - 1] == 1){
int pos = L[i][j - 1];
if(pos > 0 && a[i][pos - 1] == 0){
return false;
}
}
}
}
}
return sz;
}
