#include "soccer.h"
#include "bits/stdc++.h"
using namespace std;
struct dsu {
vector<int> p, size;
void init(int n) {
p.assign(n + 1, 0);
size.assign(n + 1, 1);
for (int i = 1; i <= n; i++) p[i] = i;
}
int get(int a) {
return (p[a] == a ? a : p[a] = get(p[a]));
}
void add(int a, int b) {
a = get(a);
b = get(b);
if (a == b) return;
if (size[a] > size[b]) swap(a, b);
size[b] += size[a];
p[a] = b;
}
};
int get(int n, vector<vector<int>> a) {
// for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) {
// cout << a[i][j];
// if (j == n - 1) cout << endl;
// }
// cout << endl;
dsu ds; ds.init(n * n);
vector<tuple<int, int, int>> ranges;
for (int i = 0; i < n; i++) {
int j = 0;
while (j < n and a[i][j]) j++;
// cout << '\t' << i << ' ' << j << ' ' << a[i][0] << endl;
// for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) {
// cout << a[i][j];
// if (j == n - 1) cout << endl;
// }
if (j == n) continue;
ranges.emplace_back(i, j, j);
while (j < n and !a[i][j]) j++;
get<2>(ranges.back()) = j - 1;
// if it contains another range?
while (j < n and a[i][j]) j++;
if (j != n) return 0;
}
// another check
// cout << ranges.size() << endl;
for (int j = 0; j < n; j++) {
int i = 0;
while (i < n and a[i][j]) i++;
if (i == n) continue;
while (i < n and !a[i][j]) i++;
while (i < n and a[i][j]) i++;
if (i != n) return 0;
}
vector<int> dx = {1, -1, 0, 0};
vector<int> dy = {0, 0, 1, -1};
pair<int, int> any;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (a[i][j]) continue;
for (int k = 0; k < 4; k++) {
auto [x, y] = make_pair(i + dx[k], j + dy[k]);
if (min(x, y) < 0 or max(x, y) >= n) continue;
if (!a[x][y]) ds.add(i * n + j, x * n + y);
}
any = make_pair(i, j);
}
}
for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) {
if (!a[i][j] and ds.get(i * n + j) != ds.get(any.first * n + any.second)) {
return 0;
}
}
int sum = 0;
for (int p1 = 0; p1 < ranges.size(); p1++) {
sum += get<2>(ranges[p1]) - get<1>(ranges[p1]) + 1;
// cout << get<0>(ranges[p1]) << ' ' << get<1>(ranges[p1]) << ' ' << get<2>(ranges[p1]) << endl;
for (int p2 = 0; p2 < ranges.size(); p2++) {
auto [i, l, shit1] = ranges[p1];
auto [j, shit2, r] = ranges[p2];
bool ok = false;
ok |= !a[i][r];
ok |= !a[j][l];
if (!ok) return 0;
}
}
// cout << sum << endl;
return sum;
}
int biggest_stadium(int n, std::vector<std::vector<int>> a) {
vector<pair<int, int>> pos;
for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) {
if (!a[i][j]) pos.emplace_back(i, j);
}
int ln = pos.size(), ans = 0;
// cout << ln << endl;
for (int bt = 0; bt < (1 << ln); bt++) {
auto b = a;
for (int k = 0; k < ln; k++) {
if (bt & (1 << k)) continue;
auto [i, j] = pos[k];
b[i][j] = 1;
}
ans = max(ans, get(n, b));
}
return ans;
}
