#include "soccer.h"
using namespace std;
#include <bits/stdc++.h>
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<bool> vb;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;
#define ALL(x) (x).begin(), x.end()
vvi f;
int n;
int TTO(int x, int y)
{
return y * n + x;
}
ii OTT(int xy)
{
return {xy % n, xy / n};
}
bool works(const vb &pos)
{
for (int i = 0; i < n * n; i++)
{
if (!pos[i])
continue;
for (int j = 0; j < n * n; j++)
{
if (!pos[j] || j < i) // remove is problems
continue;
auto [x1, y1] = OTT(i);
auto [x2, y2] = OTT(j);
if (f[x1][y1] || f[x2][y2])
throw;
int x = x1, y = y1;
bool path1 = true;
int yD = y2 > y1 ? 1 : -1;
int xD = x2 > x1 ? 1 : -1;
while (x != x2)
{
x += xD;
if (f[x][y])
{
path1 = false;
break;
}
}
while (path1 && y != y2)
{
y += yD;
if (f[x][y])
{
path1 = false;
break;
}
}
if (path1)
continue;
x = x1, y = y1;
while (y != y2)
{
y += yD;
if (f[x][y])
{
return false;
}
}
while (x != x2)
{
x += xD;
if (f[x][y])
{
return false;
}
}
}
}
return true;
}
using namespace chrono;
int biggest_stadium(int N, vvi F)
{
auto t1 = std::chrono::high_resolution_clock::now();
n = N;
f = F;
int trees = 0;
vector<bool> all(N * N);
for (int x = 0; x < n; x++)
{
for (int y = 0; y < n; y++)
{
if (F[x][y])
trees++;
else
all[TTO(x, y)] = 1;
}
}
if (works(all))
return N * N - trees;
{
auto t2 = std::chrono::high_resolution_clock::now();
std::chrono::duration<double, std::milli> fp_ms = t2 - t1;
// cerr << fp_ms.count() << endl;
if (fp_ms.count() > 3000)
return 1;
}
vector<bool> pos(N * N);
for (int c = N * N - trees; c >= 2; c--)
{
pos.assign(N * N, 0);
for (int i = 0; i < c; i++)
{
pos[N * N - 1 - i] = 1;
}
do
{
auto t2 = std::chrono::high_resolution_clock::now();
std::chrono::duration<double, std::milli> fp_ms = t2 - t1;
// cerr << fp_ms.count() << endl;
if (fp_ms.count() > 2000)
return 1;
int posi = true;
for (int i = 0; i < N * N; i++)
{
if (pos[i])
{
auto [x, y] = OTT(i);
if (F[x][y])
{
posi = false;
break;
}
}
}
if (!posi)
continue;
if (works(pos))
return c;
} while (next_permutation(ALL(pos)));
}
return 1;
}
