Editing 1275 - Jaina

== Cerinta ==

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 iesire ==

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.

== Restrictii si precizari ==

*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!

== Exemplul 1 ==

;jainain.txt

:4

:2 1 4 4 

:1

:3 3

;jainaout.txt

:Datele introduse corespund restrictiilor impuse.

:2

== Exemplul 2 ==

;jainain.txt

:0

:-1 -2 -1 0

:0

:88 90

;jainaout.txt

:Datele de intrare nu corespund restrictiilor impuse.

== Rezolvare ==

<syntaxhighlight lang="python3" line="1">

from collections import deque

def gaseste_cale(matrice, start, destinatie):
    n = len(matrice)

    # Direcțiile posibile pentru deplasare
    directii = [(-1, 0), (0, 1), (1, 0), (0, -1), (-1, -1), (-1, 1), (1, 1), (1, -1)]

    queue = deque([(start[0], start[1], 0)])  # Coada pentru BFS
    vizitat = set([(start[0], start[1])])  # Set pentru a urmări celulele vizitate

    while queue:
        x, y, pasi = queue.popleft()

        if (x, y) == destinatie:
            return pasi  # Am ajuns la destinație

        for dx, dy in directii:
            nx, ny = x + dx, y + dy

            if 0 <= nx < n and 0 <= ny < n and (nx, ny) not in vizitat:
                # Verificăm dacă există o sursă de energie la noua poziție
                if matrice[nx][ny] == 'S':
                    # Teleportăm instantaneu Jaina la sursa de energie
                    nx, ny = start

                queue.append((nx, ny, pasi + 1))
                vizitat.add((nx, ny))

    return -1  # Destinația nu poate fi atinsă

# Exemplu de utilizare
matrice = [
    ['.', '.', '.', '.', 'S', '.', '.', '.'],
    ['.', '.', '.', '.', '.', '.', '.', '.'],
    ['.', 'S', '.', '.', '.', '.', '.', '.'],
    ['.', '.', '.', '.', '.', '.', '.', '.'],
    ['.', '.', '.', '.', '.', '.', '.', '.'],
    ['.', '.', '.', '.', '.', '.', '.', '.'],
    ['.', '.', '.', '.', '.', '.', 'S', '.'],
    ['.', '.', '.', '.', '.', '.', '.', '.']
]

start = (0, 0)
destinatie = (7, 7)

rezultat = gaseste_cale(matrice, start, destinatie)

if rezultat != -1:
    print(f"Numărul minim de pași necesari: {rezultat}")
else:
    print("Destinația nu poate fi atinsă.")

</syntaxhighlight>