#include "soccer.h"
#include <bits/stdc++.h>
using namespace std;
int n;
bool check(vector<vector<int>> grid) {
if (n == 1) return 1;
int tot = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
tot += grid[i][j];
}
}
if (tot == 0) return true;
vector<int> l(n), r(n);
tot = 0;
for (int i = 0; i < n; i++) {
l[i] = r[i] = -1;
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1) continue;
if (j > 0 && grid[i][j-1] == 1 && l[i] != -1) {
return 0;
}
if (l[i] == -1) l[i] = j;
r[i] = j;
tot++;
}
}
while (l.back() == -1) {
l.pop_back();
r.pop_back();
}
reverse(l.begin(), l.end());
reverse(r.begin(), r.end());
while (l.back() == -1) {
l.pop_back();
r.pop_back();
}
reverse(l.begin(), l.end());
reverse(r.begin(), r.end());
int sz = l.size();
bool canDec = true;
for (int i = 1; i < sz; i++) {
if (l[i] > l[i-1]) {
canDec = false;
}
else if (l[i] < l[i-1]) {
if (!canDec) return 0;
}
if (l[i] > r[i-1] || r[i] < l[i-1]) return 0;
}
bool canInc = true;
for (int i = 1; i < sz; i++) {
if (r[i] < r[i-1]) {
canInc = false;
}
else if (r[i] > r[i-1]) {
if (!canInc) return 0;
}
}
for (int i = 0; i < sz; i++) {
if (l[sz-1] <= l[i]) continue;
if (r[sz-1] > r[i]) return 0;
}
for (int i = 0; i < sz; i++) {
if (r[sz-1] >= r[i]) continue;
if (l[sz-1] < l[i]) return 0;
}
return true;
}
vector<vector<int>> rotate(vector<vector<int>> grid) {
for (int i = 0; i < n / 2; i++) {
for (int j = i; j < n - i - 1; j++) {
int tmp = grid[i][j];
grid[i][j] = grid[j][n - 1 - i];
grid[j][n - 1 - i] = grid[n - 1 - i][n - 1 - j];
grid[n - 1 - i][n - 1 - j] = grid[n - 1 - j][i];
grid[n - 1 - j][i] = tmp;
}
}
return grid;
}
bool ok(vector<vector<int>> grid) {
for (int i = 0; i < 4; i++) {
grid = rotate(grid);
if (!check(grid)) return false;
}
return true;
}
int ans;
vector<int> currL, currR;
vector<vector<int>> g;
vector<vector<int>> build() {
vector<vector<int>> ret(n, vector<int>(n));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (j >= currL[i] && j <= currR[i]) ret[i][j] = 0;
else ret[i][j] = 1;
}
}
return ret;
}
void brute(int idx, int tot) {
if (idx == n) {
if (ok(build())) ans = max(ans, tot);
}
else {
for (int i = 0; i < n; i++) {
if (g[idx][i]) continue;
for (int j = i; j < n; j++) {
if (g[idx][j]) break;
currL[idx] = i;
currR[idx] = j;
brute(idx+1, tot + j - i + 1);
}
}
currL[idx] = -1;
currR[idx] = -1;
brute(idx+1, tot);
}
}
int biggest_stadium(int N, std::vector<std::vector<int>> F) {
n = N;
ans = 0;
g = F;
currL.resize(n);
currR.resize(n);
brute(0, 0);
return ans;
}
/*
int main() {
int N; cin >> N;
vector<vector<int>> grid(N, vector<int>(N));
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cin >> grid[i][j];
}
}
cout << biggest_stadium(N, grid) << "\n";
}*/
