#include <bits/stdc++.h>
#define maxn 2000
bool inside(int n, int i, int j) {
return i >= 0 && i < n && j >= 0 && j < n;
}
std::vector<std::pair<int, int>> neighs(int n, int i, int j, std::vector<std::vector<int>> &v) {
std::vector<std::pair<int, int>> sol;
for (int dy: {-1, 0, 1}) {
for (int dx: {-1, 0, 1}) {
if (abs(dy) != abs(dx) && inside(n, i+dy, j+dx) && v[i+dy][j+dx] == 0) {
sol.emplace_back(i + dy, j + dx);
}
}
}
return sol;
}
struct Pos {
int y, x;
bool isDirOrizontal, haveRemChange;
Pos(int y_, int x_, bool isdo) {
y = y_;
x = x_;
isDirOrizontal = isdo;
}
};
int viz[maxn+5][maxn+5][2]; ///punct, directie = max schimbari ramase.
bool bagat[maxn+5][maxn+5][2];
bool isFullMapOk(int n, std::vector<std::vector<int>> &v) {
std::vector<std::pair<int, std::pair<int, int>>> parti;
int i, j, z;
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
if (v[i][j] == 0) {
parti.emplace_back(neighs(n, i, j, v).size(), std::make_pair(i, j));
}
}
}
std::sort(parti.begin(), parti.end());
clock_t te = clock() + 4 * CLOCKS_PER_SEC;
for (auto p: parti) {
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
viz[i][j][0] = viz[i][j][1] = -1;
bagat[i][j][0] = bagat[i][j][1] = false;
}
}
std::queue<Pos> qu;
viz[p.second.first][p.second.second][0] = 1;
qu.emplace(p.second.first, p.second.second, false);
viz[p.second.first][p.second.second][1] = 1;
qu.emplace(p.second.first, p.second.second, true);
z = 0;
while (!qu.empty()) { ///daca nu merge campul, ma astept sa crape din cauza unui patrat cu nr mic de vecini.
z++;
if (z % 100 == 0 && clock() > te) {
return true;
}
auto now = qu.front();
qu.pop();
now.haveRemChange = viz[now.y][now.x][now.isDirOrizontal];
bagat[now.y][now.x][now.isDirOrizontal] = false;
for (int _ = 0; _ < 2; _++) {
if (_) { ///incerc sa schimb directia.
if (!now.haveRemChange) break;
now.haveRemChange = false;
now.isDirOrizontal ^= 1;
}
for (int sh: {-1, 1}) {
if (now.isDirOrizontal) now.x += sh;
else now.y += sh;
if (inside(n, now.y, now.x) && v[now.y][now.x] == 0 && viz[now.y][now.x][now.isDirOrizontal] < now.haveRemChange) {
viz[now.y][now.x][now.isDirOrizontal] = now.haveRemChange;
if (!bagat[now.y][now.x][now.isDirOrizontal]) {
qu.emplace(now.y, now.x, now.isDirOrizontal);
bagat[now.y][now.x][now.isDirOrizontal] = true;
}
}
if (now.isDirOrizontal) now.x -= sh;
else now.y -= sh;
}
}
}
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
if (v[i][j] == 0 && std::max(viz[i][j][0], viz[i][j][1]) < 0) {
return false;
}
}
}
if (clock() > te) {
break;
}
}
return true;
}
int continua(int n, std::vector<std::vector<int>> &v) {
int y = -1, x = -1, cnt0s = 0;
int i, j, z;
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
if (v[i][j] == 0) {
y = i;
x = j;
cnt0s++;
}
}
}
std::queue<std::pair<int, int>> qu;
std::vector<std::pair<int, int>> got;
qu.emplace(y, x);
got.emplace_back(y, x);
v[y][x] = -1;
while (!qu.empty()) {
std::tie(y, x) = qu.front();
qu.pop();
for (auto p: neighs(n, y, x, v)) {
if (v[p.first][p.second] != -1) {
qu.push(p);
got.push_back(p);
v[p.first][p.second] = -1;
}
}
}
for (auto &p: got) {
v[p.first][p.second] = 0;
}
return ((int)got.size() == cnt0s? cnt0s: -1);
}
int biggest_stadium(int n, std::vector<std::vector<int>> v) {
int cnt1s = 0, y = -1, x = -1;
int i, j, z;
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
if (v[i][j] == 1) {
cnt1s++;
y = i;
x = j;
}
}
}
if (cnt1s <= 1) {
if (cnt1s == 0) {
return n * n;
}
return n * n - std::min(n - x, x + 1) * std::min(n - y, y + 1);
}
///incerc sa vad daca toata harta e ok.
///zona continua?
int cnt0s = continua(n, v);
if (cnt0s == -1) {
return -1;
}
if (isFullMapOk(n, v)) {
return cnt0s;
}
return -1;
}
int main() {
std::ifstream fin("input.txt");
int n; fin >> n;
std::vector<std::vector<int>> v(n, std::vector<int>(n, 0));
int i, j, z;
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
fin >> v[i][j];
}
}
std::cout << biggest_stadium(n, v) << '\n';
fin.close();
return 0;
}
Compilation message
soccer.cpp: In function 'int continua(int, std::vector<std::vector<int> >&)':
soccer.cpp:121:12: warning: unused variable 'z' [-Wunused-variable]
121 | int i, j, z;
| ^
soccer.cpp: In function 'int biggest_stadium(int, std::vector<std::vector<int> >)':
soccer.cpp:162:12: warning: unused variable 'z' [-Wunused-variable]
162 | int i, j, z;
| ^
soccer.cpp: In function 'int main()':
soccer.cpp:201:12: warning: unused variable 'z' [-Wunused-variable]
201 | int i, j, z;
| ^
/usr/bin/ld: /tmp/ccmyfvNX.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccpsxKXU.o:soccer.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
