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:

Exemplu

turn.in

3
9 3 3 3
1 1 3
1 2 1
1 3 2
2 1 1
2 1 3
2 2 2
3 1 1
3 2 3
3 3 3
1 2 3
2 3 2
2 1 2
2 2 3
3 3 2
3 1 2
3 3 1
3 2 1
2 3 1
1 1 1
2 2 1

turn.out

11

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).

#include <bits/stdc++.h>

using namespace std;

ifstream cin("turn.in");
ofstream cout("turn.out");

struct poz
{
    int i , j , k;
};

const int dj[] = {-1 , 1 ,  0 , 0};
const int dk[] = { 0 , 0 , -1 , 1};

int n , x1 , y1 , z1 , x2 , y2 , z2 , m , p , qu , r;
int a[101][101][101];
int b[101][101][101];

queue < poz > q;

int inside(int i , int j , int k)
{
    return i >= 1 && i <= n && j >= 1 && j <= n && k >= 1 && k <= n;
}

void lee()
{
    b[x1][y1][z1]=1;
    poz r;
    r.i = x1 , r.j = y1 , r.k = z1;
    while(!q.empty())
    {
        poz r;
        r = q.front();
        if(a[r.i][r.j][r.k] == -4)
        {
            int inou = r.i;
            if(a[inou][r.j][r.k] == -4 && inou > 1) inou--;
            if(inside(inou , r.j , r.k) && a[inou][r.j][r.k] != -1 && b[inou][r.j][r.k] == 0)
            {
                q.push({inou , r.j , r.k});
                b[inou][r.j][r.k] = b[r.i][r.j][r.k] + 1;
            }
        }
        else
        {
            if(a[r.i][r.j][r.k] == -2)
            {
                int inou = r.i + 1;
                if(inside(inou , r.j , r.k) && a[inou][r.j][r.k] != -1 && b[inou][r.j][r.k] == 0)
                {
                    q.push({inou , r.j , r.k});
                    b[inou][r.j][r.k] = b[r.i][r.j][r.k] + 1;
                }
            }
            else if(a[r.i][r.j][r.k] == -3)
            {
                int inou = r.i - 1;
                if(inside(inou , r.j , r.k) && a[inou][r.j][r.k] != -1 && b[inou][r.j][r.k] == 0)
                {
                    q.push({inou , r.j , r.k});
                    b[inou][r.j][r.k] = b[r.i][r.j][r.k] + 1;
                }
            }
            for(int d = 0 ; d < 4 ; d++)
                {
                    int inou = r.i;
                    int jnou = r.j + dj[d];
                    int knou = r.k + dk[d];
                    if(inside(inou , jnou , knou) && a[inou][jnou][knou] != -1 && b[inou][jnou][knou] == 0)
                    {
                        q.push({inou , jnou , knou});
                        b[inou][jnou][knou] = b[r.i][r.j][r.k] + 1;
                    }
                }
        }
        q.pop();
    }
}

int main()
{
    cin >> n >> m >> p >> qu >> r;
    int x,y,z;
    for(int i = 1 ; i <= m ; i++)
    {
        cin >> x >> y >> z;
        a[x][y][z] = -1;
    }
    for(int i = 1 ; i <= p ; i++)
    {
        cin >> x >> y >> z;
        a[x][y][z] = -2;
    }
    for(int i = 1 ; i <= qu ; i++)
    {
        cin >> x >> y >> z;
        a[x][y][z] = -3;
    }
    for(int i = 1 ; i <= r ; i++)
    {
        cin >> x >> y >> z;
        a[x][y][z] = -4;
    }
    cin >> x1 >> y1 >> z1 >> x2 >> y2 >> z2;
    q.push({x1 , y1 , z1});
    lee();
    cout << b[x2][y2][z2];
    return 0;
}