#include "bits/stdc++.h"
using namespace std;
struct Point {
int x, y;
Point(int x, int y): x(x), y(y) {}
};
int biggest_stadium(int N, vector<vector<int>> F) {
int num_trees = 0;
for (auto i: F) for (int j: i) num_trees += j;
if (num_trees == 0) {
return N*N;
}
if (num_trees == 1) {
int x, y;
for (int i = 0; i < N; i++) for (int j = 0; j < N; j++)
if (F[i][j] == 1) {
x = i, y = j;
break;
}
return N*N - min(x + 1, N - x) * min(y + 1, N - y);
}
for (int i = 0; i < N; i++) {
F[i].insert(F[i].begin(), 1);
F[i].push_back(1);
}
F.insert(F.begin(), vector<int>(N + 2, 1));
F.push_back(vector<int>(N + 2, 1));
N += 2;
auto valid = [&](int n) {
return n >= 0 && n < N;
};
int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
vector<vector<bool>> seen(N, vector<bool>(N, false));
queue<tuple<int, int, bool>> q;
bool f1 = false, f0 = false;
for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) {
if (!f1 && F[i][j] == 1)
q.push({i, j, true}), f1 = true;
if (!f0 && F[i][j] == 0)
q.push({i, j, false}), f0 = true;
}
while (!q.empty()) {
auto [x, y, t] = q.front();
q.pop();
seen[x][y] = true;
for (auto [dx, dy]: dirs) {
int nx = x + dx, ny = y + dy;
if (valid(nx) && valid(ny) && !seen[nx][ny] && F[nx][ny] == t)
q.push({nx, ny, t});
}
}
for (int i = 0; i < N; i++) for (int j = 0; j < N; j++)
if (!seen[i][j]) return 0; // islands!!!
// most extreme zeros
Point minx = {N, N}, maxx = {0, 0}, miny = {N, N}, maxy = {0, 0};
for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) {
if (F[i][j] == 0) {
if (i < minx.x) minx = {i, j};
if (i > maxx.x) maxx = {i, j};
if (j < miny.y) miny = {i, j};
if (j > maxy.y) maxy = {i, j};
}
}
Point points[4] = {minx, maxx, miny, maxy};
for (int i = 0; i < 4; i++) for (int j = i + 1; j < 4; j++) {
if (i == j) continue;
if (F[points[i].x][points[j].y] + F[points[j].x][points[i].y] == 2) {
return 0; // 3 or more kicks
}
}
int zeros = 0;
for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) {
if (F[i][j] == 0) zeros++;
}
return zeros;
}
