#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int>> delta = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
const int MN = 2005;
int grid[MN][MN], n;
bool a[MN][MN], b[MN][MN], r[MN][MN], l[MN][MN], vis[MN][MN];
bool inside(int i, int j) {
return i >= 0 && i < n && j >= 0 && j < n;
}
void flood(int i, int j ) {
vis[i][j] = true;
for (auto [pi, pj]: delta) {
int ni = i + pi, nj = j + pj;
if (inside(ni, nj) && !vis[ni][nj] && grid[ni][nj] == 0) {
flood(ni, nj);
}
}
}
int biggest_stadium(int sz, vector<vector<int>> F) {
n = sz;
int tot = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
b[i][j] = a[i][j] = r[i][j] = l[i][j] = vis[i][j] = false;
grid[i][j] = F[i][j];
if (grid[i][j] == 0) tot++;
}
}
// Case 1: the 0s are disconnected
bool fin = false;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1 || vis[i][j]) continue;
if (fin) return tot - 1; // disconnected
flood(i, j);
fin = true;
}
}
// Case 2: there both at the right and at the left a 0 for some 1 cell
// same with above or below
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (j > 0 && l[i][j-1]) l[i][j] = true;
if (grid[i][j] == 0) l[i][j] = true;
}
for (int j = n-1; j >= 0; j--) {
if (j < n-1 && r[i][j+1]) r[i][j] = true;
if (grid[i][j] == 0) r[i][j] = true;
}
}
for (int j = 0; j < n; j++) {
for (int i = 0; i < n; i++) {
if (i > 0 && a[i-1][j]) a[i][j] = true;
if (grid[i][j] == 0) a[i][j] = true;
}
for (int i = n-1; i >= 0; i--) {
if (i < n-1 && b[i+1][j]) b[i][j] = true;
if (grid[i][j] == 0) b[i][j] = true;
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (b[i][j] && a[i][j] && grid[i][j]) {
return tot-1;
}
if (r[i][j] && l[i][j] && grid[i][j]) {
return tot-1;
}
}
}
return tot;
}
