#include "soccer.h"
#include <bits/stdc++.h>
using namespace std;
const int mxn = 2010;
const int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1};
int ldr[mxn * mxn], rnk[mxn * mxn];
int N;
int F(int x, int y) {
return x * N + y;
}
int Find(int x) {
if (ldr[x] == x) return x;
return ldr[x] = Find(ldr[x]);
}
void Union(int x, int y) {
x = Find(x), y = Find(y);
if (x == y) return;
if (rnk[y] > rnk[x]) swap(x, y);
ldr[y] = x;
rnk[x] += rnk[y];
}
int biggest_stadium(int _N, vector<vector<int>> V) {
N = _N;
auto valid = [&] (int x, int y) {
return x >= 0 && x < N && y >= 0 && y < N;
};
int SZ = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (V[i][j]) continue;
SZ++;
queue<pair<int, int>> q;
q.push({i, j});
bool visited[N][N];
memset(visited, 0, sizeof(visited));
visited[i][j] = 1;
queue<pair<int, int>> newQ;
while (q.size()) {
auto fr = q.front();
q.pop();
for (int d = 0; d < 4; d++) {
for (int mult = 1; mult < N; mult++) {
int nx = fr.first + dx[d] * mult, ny = fr.second + dy[d] * mult;
if (!valid(nx, ny) || V[nx][ny]) break;
if (visited[nx][ny]) continue;
visited[nx][ny] = 1;
newQ.push({nx, ny});
}
}
}
while (newQ.size()) {
auto fr = newQ.front();
newQ.pop();
for (int d = 0; d < 4; d++) {
for (int mult = 1; mult < N; mult++) {
int nx = fr.first + dx[d] * mult, ny = fr.second + dy[d] * mult;
if (!valid(nx, ny) || V[nx][ny]) break;
if (visited[nx][ny]) continue;
visited[nx][ny] = 1;
}
}
}
for (int l = 0; l < N; l++) {
for (int w = 0; w < N; w++) {
if (!V[l][w] && !visited[l][w]) return 0;
}
}
}
}
return SZ;
// for (int i = 0; i < N * N; i++) ldr[i] = i, rnk[i] = 1;
// int highest[N], lowest[N];
// for (int i = 0; i < N; i++) highest[i] = N + 1, lowest[i] = -1;
// auto valid = [&] (int x, int y) {
// return x >= 0 && x < N && y >= 0 && y < N;
// };
// int SZ = 0;
// for (int i = 0; i < N; i++) {
// for (int j = 0; j < N; j++) {
// if (V[i][j]) continue;
// SZ++;
// for (int d = 0; d < 4; d++) {
// int nx = i + dx[d], ny = j + dy[d];
// if (!valid(nx, ny) || V[nx][ny]) continue;
// Union(F(i, j), F(nx, ny));
// }
// }
// }
// set<int> s;
// for (int i = 0; i < N; i++) {
// for (int j = 0; j < N; j++) {
// if (V[i][j]) continue;
// s.insert(Find(F(i, j)));
// }
// }
// if (s.size() > 1 || !s.size()) return 0;
// for (int j = 0; j < N; j++) {
// bool flag = 0, obst = 0;
// for (int i = 0; i < N; i++) {
// if (V[i][j]) {
// if (flag) obst = 1;
// continue;
// }
// if (obst) return 0;
// highest[j] = min(highest[j], i);
// lowest[j] = max(lowest[j], i);
// flag = 1;
// }
// }
// for (int j = 0; j < N; j++) {
// if (highest[j] == N + 1) continue;
// pair<int, int> p = {highest[j], lowest[j]};
// j++;
// while (j < N && p == make_pair(highest[j], lowest[j])) j++;
// if (j == N || highest[j] == N + 1) return SZ;
// pair<int, int> newP = {highest[j], lowest[j]};
// if (newP.first != p.first && newP.second != p.second) return 0;
// j++;
// while (j < N && newP == make_pair(highest[j], lowest[j])) j++;
// if (j == N || highest[j] == N + 1) return SZ;
// return 0;
// }
}
