Problema Immortal – OJI 2010, Clasa a 11-a

Problema Immortal – OJI 2010, Clasa a 11-a

Rezumat

Avem o matrice cu m20m \le 20 linii și n20n \le 20 coloane. În această matrice se află k15k \le 15 nemuritori, fiecare într-o anumită celulă. La fiecare pas, doi nemuritori vecini se luptă, iar cel care pierde lupta moare. Procedeul se repetă de k1k - 1 ori, la final rămânând un singur personaj. Problema ne cere să determinăm o serie de lupte în urma căreia un singur nemuritor să rămână în viață. Pentru ca o luptă între nemuritorul de pe poziția (i,j)(i, j) și cel de pe (i1,j)(i - 1, j) să aibă loc, trebuie ca celula (i2,j)(i - 2, j) să fie liberă. Nemuritorul din (i,j)(i, j) sare peste cel din (i1,j)(i - 1, j) îl omoară, și aterizează pe (i2,j)(i - 2, j) Similar în cazul celorlalte trei direcții.

Soluție

Immortal este singura problemă de backtracking dată vreodată la OJI la clasa a 11-a. Sau cel puțin singura din ultimii 18 ani. Soluția constă în a reține într-un vector caracteristic alive ce nemuritori mai sunt încă în viață. Astfel, în cadrul funcției de backtracking vom parcurge nemuritorii vii, și pentru fiecare vom încerca să-l mutăm într-o direcție dintre cele patru. Pentru a valida în timp constant mutările, vom mai reține într-o matrice mat ce nemuritor se află în fiecare celulă. Dacă am ajuns la pasul k1k - 1 în funcția bkt, afișăm soluția generată și ne oprim.

Dacă nu am fi folosit vectorul alive, ar fi trebuit să parcurgem matricea mat în fiecare apel al funcției bkt, pentru a căuta nemuritori disponibili să se lupte, ceea ce ar fi fost ineficient. Dacă procedam așa, am fi obținut doar 90 de puncte. Cam puțin pentru o problemă de backtracking.

Sursă C++

Problema Immortal
#include <bits/stdc++.h>
using namespace std;
ifstream fin("immortal.in");
ofstream fout("immortal.out");
struct Cell { int x, y; };
struct Move { Cell a, b; };
int main() {
int m, n, k; fin >> m >> n >> k;
vector mat(m + 1, vector<int>(n + 1));
vector<Cell> imm(k + 1);
for (int i = 1; i <= k; i++) {
fin >> imm[i].x >> imm[i].y;
mat[imm[i].x][imm[i].y] = i;
}
vector<Move> ans(k);
vector<bool> alive(k + 1, true);
function<void(int)> bkt = [&](int pos) {
if (pos == k - 1) {
for (int i = 0; i < k - 1; i++) {
fout << ans[i].a.x << ' ' << ans[i].a.y << ' ';
fout << ans[i].b.x << ' ' << ans[i].b.y << '\n';
}
exit(0);
}
for (int i = 1; i <= k; i++)
if (alive[i]) {
int x = imm[i].x, y = imm[i].y;
if (x > 2 && mat[x - 1][y] && !mat[x - 2][y]) {
int j = mat[x - 1][y];
alive[j] = false; mat[x][y] = 0; mat[x - 1][y] = 0; mat[x - 2][y] = i; imm[i].x = x - 2;
ans[pos] = {{x, y}, {x - 2, y}}; bkt(pos + 1);
alive[j] = true; mat[x][y] = i; mat[x - 1][y] = j; mat[x - 2][y] = 0; imm[i].x = x;
}
if (x < m - 1 && mat[x + 1][y] && !mat[x + 2][y]) {
int j = mat[x + 1][y];
alive[j] = false; mat[x][y] = 0; mat[x + 1][y] = 0; mat[x + 2][y] = i; imm[i].x = x + 2;
ans[pos] = {{x, y}, {x + 2, y}}; bkt(pos + 1);
alive[j] = true; mat[x][y] = i; mat[x + 1][y] = j; mat[x + 2][y] = 0; imm[i].x = x;
}
if (y > 2 && mat[x][y - 1] && !mat[x][y - 2]) {
int j = mat[x][y - 1];
alive[j] = false; mat[x][y] = 0; mat[x][y - 1] = 0; mat[x][y - 2] = i; imm[i].y = y - 2;
ans[pos] = {{x, y}, {x, y - 2}}; bkt(pos + 1);
alive[j] = true; mat[x][y] = i; mat[x][y - 1] = j; mat[x][y - 2] = 0; imm[i].y = y;
}
if (y < n - 1 && mat[x][y + 1] && !mat[x][y + 2]) {
int j = mat[x][y + 1];
alive[j] = false; mat[x][y] = 0; mat[x][y + 1] = 0; mat[x][y + 2] = i; imm[i].y = y + 2;
ans[pos] = {{x, y}, {x, y + 2}}; bkt(pos + 1);
alive[j] = true; mat[x][y] = i; mat[x][y + 1] = j; mat[x][y + 2] = 0; imm[i].y = y;
}
}
};
bkt(0);
}

Dacă ai vreo nedumerire cu privire la problema Immortal, lasă un comentariu și te voi ajuta

Mulțumesc că ai citit acest articol.
Dacă vrei să susții blogul, poți cumpăra un abonament de 2$.

patreon

Lasă un comentariu!

0 comentarii