#include "soccer.h"
#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
const int N = 2e3 + 10;
int n;
vector<vector<int>> a;
vector <int> Dx = {1 , -1 , 0 , 0};
vector <int> Dy = {0 , 0 , 1 , -1};
bool marked[N][N];
bool Check(int aa , int bb)
{
if(aa < 0 || aa >= n || bb < 0 || bb >= n || marked[aa][bb] || a[aa][bb] == 1)
return false;
return true;
}
int Dfs(pair<int , int> v)
{
marked[v.F][v.S] = true;
int cnt = 1;
for(int d = 0 ; d < 4 ; d++) if(Check(v.F + Dx[d] , v.S + Dy[d]))
cnt += Dfs(make_pair(v.F + Dx[d] , v.S + Dy[d]));
return cnt;
}
int Count(int ty , int x , int y)
{
int res = 0;
if(ty == 0)
{
for(int i = 0 ; i <= x ; i++) for(int j = 0 ; j <= y ; j++)
res += (1 - a[i][j]);
}
else if(ty == 1)
{
for(int i = 0 ; i <= x ; i++) for(int j = y ; j < n ; j++)
res += (1 - a[i][j]);
}
else if(ty == 2)
{
for(int i = x ; i < n ; i++) for(int j = 0 ; j <= y ; j++)
res += (1 - a[i][j]);
}
else
{
for(int i = x ; i < n ; i++) for(int j = y ; j < n ; j++)
res += (1 - a[i][j]);
}
return res;
}
int biggest_stadium(int nn, vector<std::vector<int>> F)
{
n = nn;
a = F;
int ans = n * n;
for(int i = 0 ; i < n ; i++) for(int j = 0 ; j < n ; j++) if(a[i][j] == 1)
{
ans--;
int tmp = n * n;
for(int ty = 0 ; ty < 4 ; ty++)
tmp = min(tmp , Count(ty , i , j));
ans -= tmp;
}
ans = max(ans , 1);
pair <int , int> star;
for(int i = 0 ; i < n ; i++) for(int j = 0 ; j < n ; j++) if(a[i][j] == 0)
star = make_pair(i , j);
ans = min(ans , Dfs(star));
return ans;
}
