#include "soccer.h"
#include<bits/stdc++.h>
using namespace std;
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define P push
#define I insert
typedef long long ll;
int n,ans;
bool valid(vector<int> v){
bool arr[n][n];
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(v[i*n+j])arr[i][j]=1;
else arr[i][j]=0;
}
}
int pos[n][n][4];
for(int i=0;i<n;i++){
int cur=-1;
//left
for(int j=0;j<n;j++){
pos[i][j][0]=cur;
if(arr[i][j])cur=j;
}
cur=n;
//right
for(int j=n-1;j>=0;j--){
pos[i][j][1]=cur;
if(arr[i][j])cur=j;
}
cur=-1;
//up
for(int j=0;j<n;j++){
pos[j][i][2]=cur;
if(arr[j][i])cur=j;
}
cur=n;
//down
for(int j=n-1;j>=0;j--){
pos[j][i][3]=cur;
if(arr[j][i])cur=j;
}
}
for(int a=0;a<n;a++){
for(int b=0;b<n;b++){
if(arr[a][b]==1)continue;
for(int c=a;c<n;c++){
for(int d=b;d<n;d++){
if(arr[c][d]==1)continue;
bool ok1=false,ok2=false;
if(pos[a][b][1]>d && pos[c][d][2]<a)ok1=true;
if(pos[a][b][3]>c && pos[c][d][0]<b)ok2=true;
if(!ok1 && !ok2)return false;
}
}
}
}
return true;
}
void comput(vector<int> v,int cur,int siz){
if(cur==n*n){
if(valid(v))ans=max(ans,siz);
return;
}
if(v[cur]==-1){
v[cur]=0;
comput(v,cur+1,siz+1);
v[cur]=1;
comput(v,cur+1,siz);
v[cur]=-1;
}
else comput(v,cur+1,siz);
return;
}
int biggest_stadium(int N, vector<vector<int>> F){
n=N;
ans=0;
int trees=0;pair<int,int> tr;
for(int i=0;i<n;i++)for(int j=0;j<n;j++)if(F[i][j]){trees++;tr={i,j};}
if(trees==0)return n*n;
if(trees==1){
int x=tr.F,y=tr.S;
int a=n*x+y*(n-x) , b=n*x+(n-x)*(n-y-1) , c=n*(n-x-1)+y*(x+1) , d=n*(n-x-1)+(x+1)*(n-y-1);
return max(max(a,b),max(c,d));
}
vector<int> v;
v.assign(n*n,-1);
if(n<=3){
for(int i=0;i<n;i++)for(int j=0;j<n;j++)if(F[i][j])v[i*n+j]=1;
comput(v,0,0);
return ans;
}
for(int i=0;i<n;i++)for(int j=0;j<n;j++){
if(F[i][j])v[i*n+j]=1;
else v[i*n+j]=0;
}
if(valid(v))return n*n-trees;
else return 0;
}
