#include <bits/stdc++.h>
using namespace std;
bool DEBUG = false;
int n;
vector<pair<int, int>> TREES;
vector<vector<bool>> FIELD;
void print(pair<int, int> start, set<pair<int, int>> cover) {
if (!DEBUG) return;
if (n > 100) {
cerr << "TOO BIG!" << endl;
return;
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (start == make_pair(i, j)) cerr << "@";
else if (cover.count({i, j})) cerr << "+";
else if (FIELD[i][j]) cerr << "#";
else cerr << ".";
cerr << " ";
}
cerr << endl;
}
}
int biggest_stadium(int N, vector<vector<int>> F) {
n = N;
FIELD.assign(n, vector<bool>(n, false));
for (int i = 0; i < n; i++) for (int j = 0; j < n; j++)
if (F[i][j] == 1) {
FIELD[i][j] = true;
TREES.push_back({i, j});
}
print({-1, -1}, {});
if (TREES.size() == 0) return n * n;
if (TREES.size() == 1) {
int x = TREES[0].first, y = TREES[0].second;
n--;
int a = (abs(x - 0) + 1) * (abs(y - 0) + 1);
int b = (abs(x - 0) + 1) * (abs(y - n) + 1);
int c = (abs(x - n) + 1) * (abs(y - 0) + 1);
int d = (abs(x - n) + 1) * (abs(y - n) + 1);
n++;
return n * n - min({a, b, c, d});
}
// inefficient
int max_area = 1;
for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) {
if (FIELD[i][j]) continue;
// if (i != 3 || j != 1) continue; // TODO: REMOVE
pair<int, int> start = {i, j};
vector<vector<bool>> used(n, vector<bool>(n, false));
vector<vector<bool>> done(n, vector<bool>(n, false)); // added to the queue
set<pair<int, int>> cover;
for (int x = i; x < n; x++) {
if (FIELD[x][j]) break;
used[x][j] = true;
cover.insert({x, j});
}
for (int x = i; x >= 0; x--) {
if (FIELD[x][j]) break;
used[x][j] = true;
cover.insert({x, j});
}
for (int y = j; y < n; y++) {
if (FIELD[i][y]) break;
used[i][y] = true;
cover.insert({i, y});
}
for (int y = j; y >= 0; y--) {
if (FIELD[i][y]) break;
used[i][y] = true;
cover.insert({i, y});
}
queue<pair<int, int>> q;
q.push(start);
done[i][j] = true;
used[i][j] = true;
cover.insert(start);
const int dx[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
while (!q.empty()) {
pair<int, int> c = q.front(); q.pop();
int x = c.first, y = c.second;
bool spread = used[x][y];
if (!spread) {
bool o[4] = {false, false, false, false};
for (int k = 0; k < 4; k++) {
int nx = x + dx[k][0], ny = y + dx[k][1];
if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
if (FIELD[nx][ny]) continue;
if (used[nx][ny]) o[k] = true;
}
if ((o[0] && o[1]) || (o[1] && o[2]) || (o[2] && o[3]) || (o[3] && o[0])) spread = true;
}
if (spread) used[x][y] = true;
if (spread) cover.insert({x, y});
if (spread) {
for (int k = 0; k < 4; k++) {
int nx = x + dx[k][0], ny = y + dx[k][1];
if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
if (FIELD[nx][ny]) continue;
if (done[nx][ny]) continue;
q.push({nx, ny});
done[nx][ny] = true;
}
}
}
int a, b, c, d;
a = b = c = d = 0;
set<pair<int, int>> A, B, C, D;
for (auto [x, y]: cover) {
if (i > x && y != j) {a++; A.insert({x, y});}
if (i < x && y != j) {b++; B.insert({x, y});}
if (j > y && x != i) {c++; C.insert({x, y});}
if (j < y && x != i) {d++; D.insert({x, y});}
}
int m = cover.size() - min({a, b, c, d});
if (start == make_pair(4, 3)/*m > max_area*/) {
cerr << endl << endl;
print(start, cover);
cerr << "from: " << i << " " << j << endl;
cerr << "segment A: " << a << endl;
print(start, A);
cerr << "segment B: " << b << endl;
print(start, B);
cerr << "segment C: " << c << endl;
print(start, C);
cerr << "segment D: " << d << endl;
print(start, D);
}
// if (m > max_area) {
// // cerr << endl;
// // cerr << endl;
// // cerr << i << " " << j << endl;
// // print(start, cover);
// cerr << endl;
// cerr << endl;
// cerr << cover.size() << endl;
// cerr << a << " " << b << " " << c << " " << d << endl;
// cerr << m << endl;
// }
max_area = max({max_area, m});
if (max_area == N * N - TREES.size()) return max_area;
}
return max_area;
}
