#include "soccer.h"
#include <bits/stdc++.h>
using namespace std;
int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
int biggest_stadium(int N, std::vector<std::vector<int>> F)
{
vector<vector<bool>> vis(N, vector<bool>(N));
int cnt = 0, res = 0;
auto dfs = [&](auto& dfs, int i, int j) -> void {
vis[i][j] = 1;
for (int k = 0; k < 4; ++k) {
int ni = i + dx[k];
int nj = j + dy[k];
if (max(ni, nj) >= N || min(ni, nj) < 0 || vis[ni][nj] || F[ni][nj] == 1) continue;
dfs(dfs, ni, nj);
}
};
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
if (!vis[i][j] && F[i][j] == 0) {
dfs(dfs, i, j);
cnt += 1;
}
res += (F[i][j] == 0);
}
}
if (cnt > 1) return 0;
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
if (F[i][j] == 1) {
if (i + 1 < N && i - 1 >= 0) {
if (F[i + 1][j] + F[i - 1][j] == 0) return 0;
}
if (j + 1 < N && j - 1 >= 0) {
if (F[i][j - 1] + F[i][j + 1] == 0) return 0;
}
}
}
}
vector<array<int, 2>> pool;
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
if (F[i][j] == 0) {
pool.push_back({i, j});
}
}
}
mt19937 rng(0);
for (int it = 0; it < 10; ++it) {
deque<array<int, 3>> dq;
int idx = rng() % pool.size();
int nowi = pool[idx][0];
int nowj = pool[idx][1];
vector<vector<int>> changes(N, vector<int>(N, N * N));
dq.push_back({nowi, nowj, -1});
while (dq.size()) {
int i = dq.front()[0];
int j = dq.front()[1];
int dir = dq.front()[2];
dq.pop_front();
if (dir == -1) {
changes[i][j] = 0;
for (int k = 0; k < 4; ++k) {
int ni = i + dx[k];
int nj = j + dy[k];
if (max(ni, nj) >= N || min(ni, nj) < 0 || changes[ni][nj] <= changes[i][j] + 1 || F[ni][nj] == 1) continue;
changes[ni][nj] = changes[i][j] + 1;
dq.push_back({ni, nj, k});
}
}
for (int k = 0; k < 4; ++k) {
int ni = i + dx[k];
int nj = j + dy[k];
int add = (dir != k);
if (max(ni, nj) >= N || min(ni, nj) < 0 || changes[ni][nj] <= changes[i][j] + add || F[ni][nj] == 1) continue;
changes[ni][nj] = changes[i][j] + add;
if (add == 1) dq.push_back({ni, nj, k});
else dq.push_front({ni, nj, k});
}
// cerr << i << " " << j << " = " << changes[i][j] << "\n";
}
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
// if (F[i][j] == 1) cerr << "- ";
// else cerr << changes[i][j] << " ";
if (F[i][j] == 0 && changes[i][j] > 2) {
res = 0;
}
}
// cerr << "\n";
}
// cerr << "\n";
}
return res;
}
