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 :smile:

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