Problema Immortal – OJI 2010, Clasa a 11-a
Rezumat
Avem o matrice cu linii și coloane. În această matrice se află nemuritori, fiecare într-o anumită celulă. La fiecare pas, doi nemuritori vecini se luptă, iar cel care pierde lupta moare. Procedeul se repetă de 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 cel de pe să aibă loc, trebuie ca celula să fie liberă. Nemuritorul din sare peste cel din îl omoară, și aterizează pe 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 î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 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 
