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.

Exemplu Immortal

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!

PayPal