#include "soccer.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 30;
bool f[N][N];
int prefix[N][N];
int n;
pair<int, bool> dp[N][N][N][N];
int get_sum(int i, int l, int r){
if(l == 0)
return prefix[i][r];
return prefix[i][r] - prefix[i][l - 1];
}
bool bad(int l1, int r1, int l2, int r2){
if(l1 <= l2 && r2 <= r1)
return false;
if(l2 <= l1 && r1 <= r2)
return false;
return true;
}
int solve(int i, int j, int l, int r){
auto &[ans, solved] = dp[i][j][l][r];
if(solved)
return ans;
ans = 0;
solved = true;
if(l != r){
ans = max(ans, solve(i, j, l + 1, r));
ans = max(ans, solve(i, j, l, r - 1));
}
if(i != 0){
int sum = get_sum(i - 1, l, r);
if(!sum){
ans = max(ans, solve(i - 1, j, l, r) + r - l + 1);
}
}
if(j != n - 1){
int sum = get_sum(j + 1, l, r);
if(!sum){
ans = max(ans, solve(i, j + 1, l, r) + r - l + 1);
}
}
return ans;
}
int biggest_stadium(int _N, std::vector<std::vector<int>> F){
n = _N;
for(int i = 0; i < n; ++i)
for(int j = 0; j < n; ++j)
f[i][j] = F[i][j];
for(int i = 0; i < n; ++i){
prefix[i][0] = f[i][0];
for(int j = 1; j < n; ++j)
prefix[i][j] = prefix[i][j - 1] + f[i][j];
}
int ans = 0;
for(int i = 0; i < n; ++i){
for(int l = 0; l < n; ++l){
for(int r = l; r < n; ++r){
if(f[i][r])
break;
ans = max(ans, solve(i, i, l, r) + r - l + 1);
}
}
}
return ans;
}
/*
3
1 1 1
1 1 1
1 1 1
*/
