#include "soccer.h"
#include <bits/stdc++.h>
using namespace std;
bool check2(vector<vector<bool>> &includes, int a, int b, int c, int d) {
if (a == c) {
for (int i = min(b, d) + 1; i < max(b, d); ++i) {
if (!includes[a][i]) return false;
}
return true;
} else if (b == d) {
for (int i = min(a, c) + 1; i < max(a, c); ++i) {
if (!includes[i][b]) return false;
}
return true;
}
// x first
if (c > a) swap(a, c), swap(b, d);
bool ok = true;
for (int i = a; i >= c; --i) {
if (!includes[i][b]) {
ok = false;
break;
}
}
if (ok) {
for (int i = min(b, d); i <= max(b, d); ++i) {
if (!includes[c][i]) {
ok = false;
break;
}
}
}
if (ok) return true;
// x first2
if (c < a) swap(a, c), swap(b, d);
ok = true;
for (int i = a; i <= c; ++i) {
if (!includes[i][b]) {
ok = false;
break;
}
}
if (ok) {
for (int i = min(b, d); i <= max(b, d); ++i) {
if (!includes[c][i]) {
ok = false;
break;
}
}
}
if (ok) return true;
// y first
ok = true;
if (d < b) swap(a, c), swap(b, d);
for (int i = b; i <= d; ++i) {
if (!includes[a][i]) {
ok = false;
break;
}
}
if (ok) {
for (int i = min(a, c); i <= max(a, c); ++i) {
if (!includes[i][d]) {
ok = false;
break;
}
}
}
return ok;
}
bool check(vector<vector<bool>> &includes) {
int n = includes.size();
for (int a = 0; a < n; ++a) {
for (int b = 0; b < n; ++b) {
if (!includes[a][b]) continue;
for (int c = a; c < n; ++c) {
for (int d = 0; d < n; ++d) {
if (a == c && d == 0) {
d = b;
continue;
}
if (!includes[c][d]) continue;
if (!check2(includes, a, b, c, d)) return false;
}
}
}
}
return true;
}
int solve(vector<vector<bool>> &includes, int cnt) {
int n = includes.size();
if (cnt == 1) return 1;
if (check(includes)) return cnt;
int res = 0;
for (int a = 0; a < n; ++a) {
for (int b = 0; b < n; ++b) {
if (!includes[a][b]) continue;
includes[a][b] = false;
res = max(res, solve(includes, cnt - 1));
includes[a][b] = true;
if (res == cnt - 1) return res;
}
}
return res;
}
int biggest_stadium(int N, std::vector<std::vector<int>> F)
{
int cnt = 0;
vector<vector<bool>> f(N, vector<bool>(N, false));
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
if (!F[i][j]) ++cnt;
f[i][j] = !F[i][j];
}
}
if (check(f)) return cnt;
return cnt - 1;
}
