#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;
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;
};
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (V[i][j]) continue;
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 1;
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 1;
return 0;
}
}
