#include <iostream>
#include <vector>
using namespace std;
void backtrack(vector<vector<vector<int>>>& combinations, vector<vector<int>> toCombine, int itemsLeft, vector<vector<int>> currentCombination) {
if (itemsLeft == 0) {
combinations.push_back(currentCombination);
return;
}
for (int i = 0; i < toCombine.size(); i++) {
vector<vector<int>> currentCombinationClone = currentCombination;
vector<vector<int>> toCombineClone = toCombine;
currentCombinationClone.push_back(toCombine[i]);
toCombineClone.erase(toCombineClone.begin() + i);
backtrack(combinations, toCombineClone, itemsLeft - 1, currentCombinationClone);
}
}
bool checkValidity(vector<vector<int>> s, vector<vector<int>> F) {
vector<vector<vector<int>>> combinations;
backtrack(combinations, s, 2, {});
/*for (vector<vector<int>> x : combinations) {
cout << x[0][0] << " " << x[0][1] << " ; " << x[1][0] << " " << x[1][1] << endl;
}*/
for (vector<vector<int>> comb : combinations) {
bool validCombination = false;
//cout << comb[0][0] << " " << comb[0][1] << " ; " << comb[1][0] << " " << comb[1][1] << endl;
// misma fila
if (comb[0][1] == comb[1][1]) {
bool foundShit = false;
int starter, ender;
if (comb[0][0] > comb[1][0]) {
starter = comb[1][0];
ender = comb[0][0];
} else {
starter = comb[0][0];
ender = comb[1][0];
}
for (int i = starter; i <= ender; i++) {
if (F[i][comb[0][1]] == 1) {
foundShit = true;
break;
}
}
if (!foundShit) {
validCombination = true;
} else {
return false;
}
}
// misma columna
if (comb[0][0] == comb[1][0]) {
bool foundShit = false;
int starter, ender;
if (comb[0][0] > comb[1][0]) {
starter = comb[1][0];
ender = comb[0][0];
} else {
starter = comb[0][0];
ender = comb[1][0];
}
for (int i = starter; i <= ender; i++) {
if (F[i][comb[0][0]] == 1) {
foundShit = true;
break;
}
}
if (!foundShit) {
validCombination = true;
} else {
return false;
}
}
// 2 movimientos
// primero c despues r
int starter, ender;
if (comb[0][0] > comb[1][0]) {
starter = comb[1][0];
ender = comb[0][0];
} else {
starter = comb[0][0];
ender = comb[1][0];
}
// cout << starter << ", " << ender << endl;
bool foundShit = false;
for (int i = starter; i <= ender; i++) {
//cout << i << ", " << comb[0][1] << ", " << F[i][comb[0][1]] << endl;
if (F[i][comb[0][1]] == 1) {
//cout << "autista1" << endl;
foundShit = true;
break;
}
}
if (!foundShit) {
int currentY = comb[1][1];
if (comb[0][1] > comb[1][1]) {
starter = comb[0][1];
ender = comb[1][1];
} else {
starter = comb[1][1];
ender = comb[0][1];
}
//cout << starter << ", " << ender << ", " << currentY << endl;
bool foundShit = false;
for (int i = starter; i <= ender; i++) {
if (F[currentY][i] == 1) {
//cout << "autista2" << endl;
//cout << "err2" << endl;
foundShit = true;
break;
}
}
if (!foundShit) {
validCombination = true;
}
}
// ahora primero r y despues c
if (comb[0][1] > comb[1][1]) {
starter = comb[1][1];
ender = comb[0][1];
} else {
starter = comb[0][1];
ender = comb[1][1];
}
//cout << starter << ", " << ender << endl;
foundShit = false;
for (int i = starter; i <= ender; i++) {
if (F[comb[0][0]][i] == 1) {
//cout << "autista3" <<endl;
foundShit = true;
break;
}
}
if (!foundShit) {
int currentY = comb[1][0];
if (comb[0][0] > comb[1][0]) {
starter = comb[1][0];
ender = comb[0][0];
} else {
starter = comb[0][0];
ender = comb[1][0];
}
bool foundShit = false;
for (int i = starter; i <= ender; i++) {
if (F[i][currentY] == 1) {
//cout << "autista4" <<endl;
foundShit = true;
break;
}
}
if (!foundShit) {
validCombination = true;
}
}
// validacion
if (!validCombination) {
//cout << comb[0][0] << " " << comb[0][1] << " ; " << comb[1][0] << " " << comb[1][1] << endl;
return false;
}
}
return true;
}
bool present(vector<vector<int>> where, vector<int> what) {
for (vector<int> x : where) {
if (x[0] == what[0] && x[1] == what[1]) {
return true;
}
}
return false;
}
int biggest_stadium(int N, vector<vector<int>> F) {
vector<int> sValues;
for (int x = 0; x < N; x++) {
for (int y = 0; y < N; y++) {
vector<vector<int>> currentCells = {{x, y}};
if (F[x][y] == 1) {
continue;
}
bool foundExpansion = true;
while (foundExpansion) {
foundExpansion = false;
for (vector<int> cell : currentCells) {
// derecha
if (cell[0] != N - 1 && F[cell[0] + 1][cell[1]] == 0 && !present(currentCells, {cell[0] + 1, cell[1]})) {
//cout << "a" << endl;
vector<vector<int>> currentCellsClone = currentCells;
currentCellsClone.push_back({cell[0] + 1, cell[1]});
/*for (vector<int> x: currentCells) {
cout << x[0] << ", " << x[1] << ", ";
}*/
if (checkValidity(currentCellsClone, F)) {
currentCells = currentCellsClone;
foundExpansion = true;
break;
}
}
// izquierda
if (cell[0] != 0 && F[cell[0] - 1][cell[1]] == 0 && !present(currentCells, {cell[0] - 1, cell[1]})) {
//cout << "b" << endl;
vector<vector<int>> currentCellsClone = currentCells;
currentCellsClone.push_back({cell[0] - 1, cell[1]});
if (checkValidity(currentCellsClone, F)) {
currentCells = currentCellsClone;
foundExpansion = true;
break;
}
}
// arriba
if (cell[1] != 0 && F[cell[0]][cell[1] - 1] == 0 && !present(currentCells, {cell[0], cell[1] - 1})) {
//cout << "c" << endl;
vector<vector<int>> currentCellsClone = currentCells;
currentCellsClone.push_back({cell[0], cell[1] - 1});
if (checkValidity(currentCellsClone, F)) {
currentCells = currentCellsClone;
foundExpansion = true;
break;
}
}
// abajo
if (cell[1] != N - 1 && F[cell[0]][cell[1] + 1] == 0 && !present(currentCells, {cell[0], cell[1] + 1})) {
//cout << "d" << endl;
vector<vector<int>> currentCellsClone = currentCells;
currentCellsClone.push_back({cell[0], cell[1] + 1});
if (checkValidity(currentCellsClone, F)) {
currentCells = currentCellsClone;
foundExpansion = true;
break;
}
}
// arriba derecha
if (cell[0] != N - 1 && cell[1] != 0 && F[cell[0] + 1][cell[1] - 1] == 0 && !present(currentCells, {cell[0] + 1, cell[1] - 1})) {
//cout << "e" << endl;
vector<vector<int>> currentCellsClone = currentCells;
currentCellsClone.push_back({cell[0] + 1, cell[1] - 1});
/*for (vector<int> x: currentCells) {
cout << x[0] << ", " << x[1] << ", ";
}
cout << endl;*/
if (checkValidity(currentCellsClone, F)) {
currentCells = currentCellsClone;
foundExpansion = true;
break;
}
}
// arriba izquierda
if (cell[0] != 0 && cell[1] != 0 && F[cell[0] - 1][cell[1] - 1] == 0 && !present(currentCells, {cell[0] - 1, cell[1] - 1})) {
//cout << "f" << endl;
vector<vector<int>> currentCellsClone = currentCells;
currentCellsClone.push_back({cell[0] - 1, cell[1] - 1});
if (checkValidity(currentCellsClone, F)) {
currentCells = currentCellsClone;
foundExpansion = true;
break;
}
}
// abajo derecha
if (cell[0] != N - 1 && cell[1] != N - 1 && F[cell[0] + 1][cell[1] + 1] == 0 && !present(currentCells, {cell[0] + 1, cell[1] + 1})) {
//cout << "g" << endl;
vector<vector<int>> currentCellsClone = currentCells;
currentCellsClone.push_back({cell[0] + 1, cell[1] + 1});
if (checkValidity(currentCellsClone, F)) {
currentCells = currentCellsClone;
foundExpansion = true;
break;
}
}
// abajo izquierda
if (cell[0] != 0 && cell[1] != N - 1 && F[cell[0] - 1][cell[1] + 1] == 0 && !present(currentCells, {cell[0] - 1, cell[1] + 1})) {
//cout << "h" << endl;
vector<vector<int>> currentCellsClone = currentCells;
currentCellsClone.push_back({cell[0] - 1, cell[1] + 1});
if (checkValidity(currentCellsClone, F)) {
currentCells = currentCellsClone;
foundExpansion = true;
break;
}
}
}
}
sValues.push_back(currentCells.size());
}
}
int m = sValues[0];
for (int x : sValues) {
if (x > m) {
m = x;
}
}
return m;
}
Compilation message
soccer.cpp: In function 'void backtrack(std::vector<std::vector<std::vector<int> > >&, std::vector<std::vector<int> >, int, std::vector<std::vector<int> >)':
soccer.cpp:11:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
11 | for (int i = 0; i < toCombine.size(); i++) {
| ~~^~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
223 ms |
520 KB |
ok |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
344 KB |
wrong |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
344 KB |
wrong |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
223 ms |
520 KB |
ok |
| 2 |
Incorrect |
2 ms |
344 KB |
wrong |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
223 ms |
520 KB |
ok |
| 2 |
Incorrect |
2 ms |
344 KB |
wrong |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
223 ms |
520 KB |
ok |
| 2 |
Incorrect |
2 ms |
344 KB |
wrong |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
223 ms |
520 KB |
ok |
| 2 |
Incorrect |
2 ms |
344 KB |
wrong |
| 3 |
Halted |
0 ms |
0 KB |
- |
