Cerința

Eroul nostru Susan se află într-un turn de formă cubică, de latură n. El dorește să ajungă la comoara ascunsă în interiorul turnului. Din fericire, Susan a făcut rost de o hartă care îi indică cu exactitate coordonatele locului în care se află comoara din turn. Eroul nostru vrea să știe care este distanța minimă pe care o poate parcurge pentru a ajunge la comoară.

Turnul este împărțit în n etaje, iar fiecare etaj este împărțit în n x n celule (camere). O cameră poate:

fi blocată, astfel fiind inaccesibilă eroului nostru
fi accesibilă, astfel eroul nostru poate intra în aceasta
conține o scară ascendentă care îl poate duce pe erou cu un etaj mai sus, în camera situată deasupra camerei curente
conține o scară descendentă care îl poate duce pe erou cu un etaj mai jos, în camera situată sub camera curentă
conține o trapă prin care eroul va cădea la etajul inferior, în camerele situate sub camera curentă (dacă eroul, în urma căderii, se află într-o cameră ce conține o trapă, el va continua să cadă până se va afla într-o o cameră fără trapă, pe aceeași coloană)

La fiecare trecere dintr-o cameră în alta, eroul execută un pas.

Fiind date latura turnului și coordonatele zidurilor, scărilor, gropilor, eroului și a comorii, se cere să se afișeze numărul minim de pași pe care îl poate parcurge Susan pentru a ajunge la comoară.

Date de intrare

Fișierul de intrare turn.in conține:

pe prima linie numărul n, reprezentând lungimea laturii turnului.
pe a doua linie se află numărul z, reprezentând numărul de ziduri, numărul s1, reprezentând numărul de scări descendente, numărul s2, reprezentând numărul de scări descendente și numărul g, reprezentând numărul de gropi.
pe următoarele z linii se află coordonatele zidurilor.
pe următoarele s1 linii se află coordonatele scărilor ascendente.
pe următoarele s2 linii se află coordonatele scărilor descendente.
pe următoarele g linii se află coordonatele gropilor.
pe penultima linie se află coordonatele eroului, iar pe ultima linie se află coordonatele comorii.

Date de ieșire

Fișierul de ieșire turn.out va conține numărul minim de pași pe care îl poate face Susan pentru a ajunge la comoara sa.

Restricții și precizări

1 ≤ n ≤ 100
1 ≤ z ≤ 30000
1 ≤ s1 ≤ s2 ≤ 200
1 ≤ g ≤ 10000
Se garantează că există soluție pentru toate datele de test.
Poziția inițială se consideră a fi situată la pasul 1.
Trapa generează o cădere a eroului pe verticală, până când ajunge într-o cameră fără trapă.

Exemplu

turn.in

turn.out

Explicație

Turnul are 3 etaje. Susan pleacă din celula de coordonate (1 1 1), iar celula în care se află comoara are coordonatele (2 2 1). Există 9 celule în care se află ziduri, 3 celule în care se află scări ascendente, 3 celule în care se află scări descendente și 3 celule în care se află gropi. Traseul cel mai scurt trece prin 11 camere: (1 1 1) (1 1 2) (1 2 2) (1 2 3) (2 2 3) (2 3 3) (2 3 2) (3 3 2) (3 2 2) (3 2 1) (2 2 1).

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema Susan :

/**
Problema Turn - Constantinescu Eduard
Inspirata din problema Traseu - Carmen Minca
Algoritm de rezolvare: Lee cu mici modificari
Complexitate Timp O(n*n*n)
*/


#include <bits/stdc++.h>

using namespace std;

FILE *fin = fopen("turn.in", "r");
FILE *fout = fopen("turn.out", "w");

int n;

struct
{
    int prop, val;
    ///prop = 1 => scara sus
    ///prop = 2 => scara jos
    ///prop = 3 => groapa
    ///prop = 0 => gol
} cub[105][105][105];

struct
{
    int x, y, z; ///coordonatele in cub
} C[105*105*105], vec, poz, sf;

int dx[] = {1, 0, 0, 0, 0, -1}; ///cele 4 directii
int dy[] = {0, 0, -1, 0, 1, 0};
int dz[] = {0, 1, 0, -1, 0, 0};

/**


dx = 1 0 0 0 0 -1
dy = 0 0-1 0 1 0
dz = 0 1 0-1 0 0

x = sus
y = dreapta
z = spate

*/

void bordare() ///bordare simpla a matricei
{
    register int i, j;
    for(i = 0; i <= n+1; i++)
        for(j = 0; j <= n+1; j++)
        {
            cub[i][0][j].val = -1;
            cub[i][n+1][j].val = -1;
        }
    for(i = 0; i <= n+1; i++)
        for(j = 0; j <= n+1; j++)
        {
            cub[i][j][n+1].val = -1;
            cub[i][j][0].val = -1;
        }
    for(i = 0; i <= n+1; i++)
        for(j = 0; j <= n+1; j++)
        {
            cub[n+1][i][j].val = -1;
            cub[0][i][j].val = -1;
        }
}

void citire()
{
    int z, s, j, o;
    fscanf(fin, "%d%d%d%d%d", &n, &z, &s, &j, &o); ///citirea valorilor
    int a, b, c;
    for(int i = 1; i <= z; i++) /// se citesc coord ziduri
    {
        fscanf(fin, "%d%d%d", &a, &b, &c);
        cub[a][b][c].val = -1;
    }
    for(int i = 1; i <= s; i++)/// se citesc coord scari sus
    {
        fscanf(fin, "%d%d%d", &a, &b, &c);
        cub[a][b][c].prop = 1;
    }
    for(int i = 1; i <= j; i++)/// se citesc coord scari jos
    {
        fscanf(fin, "%d%d%d", &a, &b, &c);
        cub[a][b][c].prop = 2;
    }
    for(int i = 1; i <= o; i++)/// se citesc coord gropi
    {
        fscanf(fin, "%d%d%d", &a, &b, &c);
        cub[a][b][c].prop = 3;
    }

    fscanf(fin, "%d%d%d", &poz.x, &poz.y, &poz.z); ///se citesc coord
    fscanf(fin, "%d%d%d", &sf.x, &sf.y, &sf.z); /// de inceput si sf

}

void rezolvare() ///un lee cu mici modificari
{
    int prim, ultim, k, s = 1, l;

    prim = ultim = 0;
    C[0] = poz;
    cub[poz.x][poz.y][poz.z].val = 1; ///marcam pozitia de inceput

    while(prim <= ultim && cub[sf.x][sf.y][sf.z].val == 0) /// cat timp am el in coada
    {
        ///si nu am ajuns la sf
        poz = C[prim];
        ++prim; /// extrag din coada

        if(cub[poz.x][poz.y][poz.z].prop == 3) ///este groapa
        {
            int d = 0;
            vec = poz; /// pornim de la pozitia gropii
            while(vec.x > 1 && cub[vec.x][vec.y][vec.z].prop == 3)
                --vec.x, d++;///cat timp suntem in cub si suntem pe o groapa, vom cadea
            if(cub[vec.x][vec.y][vec.z].val == 0) ///este liber
            {
                cub[vec.x][vec.y][vec.z].val = cub[poz.x][poz.y][poz.z].val+d;
                ultim++;///marchez drumul si adaug in coada
                C[ultim] = vec;
            }
        }

        else
        {
            if(cub[poz.x][poz.y][poz.z].prop == 1)
                {
                    k = 0;
                    l = 4;
                }
            else if(cub[poz.x][poz.y][poz.z].prop == 2)
            {
                k = 1;
                l = 5;
            }
            else
            {
                k = 1;
                l = 4;
            }
            for(k; k <= l; k++) ///parcurg in cele 4 directii posibile
            {
                vec.x = poz.x + dx[k];
                vec.y = poz.y + dy[k];
                vec.z = poz.z + dz[k];
                if(cub[vec.x][vec.y][vec.z].val == 0)///este liber
                {
                    cub[vec.x][vec.y][vec.z].val = cub[poz.x][poz.y][poz.z].val + 1;
                    ultim++; ///marchez drumul si adaug in coada
                    C[ultim] = vec;
                }
            }

        }
    }
    fprintf(fout, "%d\n", cub[sf.x][sf.y][sf.z].val);
    ///afisez rezultatul
}

int main()
{
    citire();
    bordare();
    rezolvare();
    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #1337 Susan

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1337 Susan de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #1337 Susan