#include "soccer.h"
#include <cstdio>
#include <vector>
using namespace std;
// <|°_°|>
const int MAX_ROWS = 2001;
bool Empty[MAX_ROWS][MAX_ROWS];
bool Check(int up, int down, int left, int right) {
// printf("CHECKING : %d %d %d %d\n", up, down, left, right);
int highest = -1;
int low = 1e9;
int leftBorder = 1e9, rightBorder = -1;
for (int i = up; i < down && highest < 0; i ++)
{
for (int j = left; j < right; j ++)
{
if (Empty[i][j])
{
highest = i;
leftBorder = min(leftBorder, j);
if (rightBorder >= 0 && rightBorder < (j - 1))
return 0;
rightBorder = j;
int cur = i;
while (Empty[cur][j])
cur ++;
low = min(low, cur);
while (cur < down)
if (Empty[cur ++][j])
return 0;
}
}
}
rightBorder ++;
if (highest < 0)
{
// printf("DONE\n");
return 1;
}
for (int i = up; i < low; i ++)
{
int j = left;
while (!Empty[i][j])
j ++;
for (; j < right - 1; j ++)
if (!Empty[i][j] && Empty[i][j + 1])
return 0;
}
for (int i = low; i < down; i ++)
{
for (int j = left; j < right; j ++)
{
if (Empty[i][j] && (j < leftBorder || j >= rightBorder))
return 0;
}
}
return Check(up, low, left, leftBorder) && Check(up, low, rightBorder, right) && Check(low, down, leftBorder, rightBorder);
}
int biggest_stadium(int nbRows, vector <vector <int>> Forest) {
int nb = 0;
for (int i = 0; i < nbRows; i ++)
for (int j = 0; j < nbRows; j ++)
nb += Empty[i][j] = !Forest[i][j];
return Check(0, nbRows, 0, nbRows) ? nb : 0;
}
