Cerința

Jaina se află în Theramore Isle și trebuie să ajungă la mentorul ei, Antonidas. Aceștia se află într-o matrice pătratică de dimensiune n x n, în poziții de coordonate cunoscute.

Jaina se poate deplasa în oricare dintre cele 8 direcții. Astfel, dacă inițial ea se găsește în celula de coordonate (x, y), poate ajunge în oricare dintre celulele (x-1, y-1), (x-1, y), (x-1, y + 1), (x, y + 1), (x + 1, y + 1), (x + 1, y), (x + 1, y - 1) sau (x, y - 1) făcând exact un pas.

În anumite celule se află câte o sursă de energie. Fiecare sursă emite raze în patru direcții (N, E, S, V), fiecare rază ajungând până la marginea matricei.

Când Jaina pășește pe o astfel de rază, ea se teleportează obligatoriu în celula sursei razei respective, deci nu este posibilă trecerea dincolo de aceste raze decât prin punctul sursă. Teleportarea este automată și instantanee și nu se consideră ca fiind un pas al Jainei.

Antonidas vă roagă să o ajutați pe Jaina să ajungă la el, efectuând un număr minim de pași!

Date de intrare

Fișierul de intrare jaina.in conține pe prima linie numărul n, iar pe a doua linie 4 numere naturale separate prin spații, care semnifică coordonatele celulei în care se află Jaina și coordonatele celulei în care se află Antonidas. ( 2 perechi linie-coloană )

A treia linie conține numărul m de surse de energie.

Pe următoarele m linii se află câte două numere naturale x y, reprezentând coordonatele fiecărei surse.

Date de ieșire

Fișierul de ieșire jaina.out va conține pe prima linie numărul nrp, reprezentând numărul minim de pași pe care Jaina trebuie să-i efectueze pentru a ajunge la Antonidas.

Restricții și precizări

1 ≤ n ≤ 100
1 ≤ m ≤ 10
Orice celulă are dimensiunea 1x1
În cazul în care Jaina se află la intersecția a două raze de surse diferite, aceasta se va teleporta la sursa de linie minimă.
Nu există două surse care să se afle pe aceeași linie sau pe aceeași coloană.
Se garantează că există soluție pentru toate testele.
Antonidas promite că o să fiți răsplătiți cu o minge de foc dacă găsiți răspunsul corect la această problemă.
Deoarece Jaina este disperată, limitele de memorie sunt foarte mari, însă pe viitor nu este garantat acest lucru!

Exemplu

jaina.in

jaina.out

Explicație

Numărul de pași necesari în acest caz este 2.

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 Jaina:

#include <fstream>
#include <queue>

using namespace std;

ifstream fin("jaina.in");
ofstream fout("jaina.out");

#define MaxN 101
#define INF 0x3f3f3f3f

int n;
int ip, jp, is, js;
int a[MaxN][MaxN];
int m;
int x, y;

struct Coord
{
    int x, y;
} source[MaxN][MaxN];

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

queue<pair<int, int> >Q;

void Read();
void Laser_fill(int, int);
void Init();
void Lee();
bool Ok(int, int);

int main()
{
    Read();
    Lee();
    fout << a[is][js] << '\n';

    fin.close();
    fout.close();
    return 0;
}

void Read()
{
    fin >> n;

    Init();

    fin >> ip >> jp >> is >> js;

    fin >> m;

    for (int i = 1; i <= m; ++i)
    {
        fin >> x >> y;
        Laser_fill(x, y);
    }
}

void Laser_fill(int x, int y)
{
    for (int i = 1; i <= n; ++i)
    {
        a[x][i] = -1;

        if (!source[x][i].x)
            source[x][i].x = INF;
        
        if ( source[x][i].x > x )
            source[x][i].x = x;
        source[x][i].y = y;

        a[i][y] = -1;

        if (!source[i][y].x)
            source[i][y].x = INF;
        
        if ( source[i][y].x > x )
            source[i][y].x = x;
        source[i][y].y = y;

    }

    a[x][y] = INF;
}

void Init()
{
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            a[i][j] = INF;
}


void Lee()
{
    Q.push({ ip,jp });
    a[ip][jp] = 0;

    while (!Q.empty())
    {
        int i = Q.front().first;
        int j = Q.front().second;
        Q.pop();

        for (int d = 0; d < 8; ++d)
        {
            int iv = i + di[d];
            int jv = j + dj[d];

            int x_sursa = source[iv][jv].x;
            int y_sursa = source[iv][jv].y;

            if (a[iv][jv] == -1 && a[x_sursa][y_sursa] > a[i][j] + 1)
            {
                a[x_sursa][y_sursa] = a[i][j] + 1;
                Q.push({ x_sursa, y_sursa });
            }
            else

                if (Ok(iv, jv) && a[iv][jv] > a[i][j] + 1)
                {
                    a[iv][jv] = a[i][j] + 1;
                    Q.push({ iv,jv });
                }

        }
    }
}

bool Ok(int i, int j)
{
    if (i < 1 || i > n || j < 1 || j > n)
        return false;
    if (a[i][j] == -1)
        return false;
    return true;
}

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 #1275 Jaina

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1275 Jaina 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 #1275 Jaina