Rezumat Immortal
Avem o matrice cu $m \le 20$ linii și $n \le 20$ coloane. În această matrice se află $k \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 $k - 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 cel de pe $(i - 1, j)$ să aibă loc, trebuie ca celula $(i - 2, j)$ să fie liberă. Nemuritorul din $(i, j)$ sare peste cel din $(i - 1, j)$, îl omoară, și aterizează pe $(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 $k - 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++
#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<vector<int>> 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';
}
fout.close();
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 
Îți place conținutul acestui site?
Dacă vrei să mă susții în întreținerea server-ului și în a scrie mai multe articole de calitate pe acest blog, mă poți ajuta printr-o mică donație!
