Vizualizare sursă pentru „2041 - Camelot”

= Cerința =
Regele Arthur – Inimă de Leu, vrea să adune la castel toţi cavalerii ''Mesei Rotunde'' pentru a hotărî împreună soarta regatului. Dar cavalerii nu se află toţi în ''Camelot'' şi durează un timp până vor ajunge la castel din pădurea care înconjoară castelul.

Harta pădurii are forma unei matrici, cu <code>m</code> linii şi <code>n</code> coloane. Pentru fiecare cavaler care nu este în ''Camelot'' se cunosc coordonatele <code>x y</code>, reprezentând linia şi coloana din matrice în care se află iniţial cavalerul. Toţi cavalerii pornesc simultan spre castel, iar fiecare cavaler se deplasează după regula de deplasare a calului de la jocul de şah.

Cunoscând dimensiunile <code>mxn</code> ale matricei, coordonatele castelului şi cele ale cavalerilor, se cere să se determine:

1. numărul minim de mutări după care va ajunge la castel unul dintre cavaleri

2. numărul minim de mutări după care toţi cavalerii se vor afla la castel.

De exemplu, în imaginea de mai sus este reprezentată harta sub forma unei matrici de tip <code>8x8</code>, iar castelul are coordonatele <code>4 5</code> (linia <code>4</code> şi coloana <code>5</code>), primul cavaler se află iniţial în punctul de coordonate <code>1 2</code> iar cel de al doilea în punctul <code>8 1</code>. Primul cavaler va ajunge la castel din minim <code>2</code> deplasări, iar al doilea după minim <code>4</code> mutări Pentru prima întrebare răspunsul este <code>2</code>, iar pentru a doua întrebare răspunsul este <code>4</code>.

= Date de intrare =
Fișierul de intrare <code>camelotIN.txt</code> conține pe prima linie numărul <code>p</code>, pentru toate testele de intrare numărul <code>p</code> putând avea doar valoarea <code>1</code> sau valoarea <code>2</code>.

Pe cea de a doua linie sunt scrise numerele naturale <code>m n k</code>, separate prin câte un spaţiu, iar pe a treia linie se află coordonatele <code>xc yc</code> ale castelului. Pe următoarele <code>k</code> linii se află <code>k</code> perechi de numere întregi <code>x[i] y[i]</code> (<code>1 ≤ i ≤ k</code>), separate prin câte un spaţiu, reprezentând coordonatele cavalerilor.

= Date de ieșire =
Fișierul de ieșire <code>camelotOUT.txt</code> va conține pe prima linie:

* pentru <code>p=1</code>, pe prima linie se va scrie numărul minim de mutări după care va ajunge unul din cavaleri
* pentru <code>p=2</code>, pe prima linie se va scrie numărul minim de mutări după care vor ajunge toţi cavalerii. În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

= Restricții și precizări =

* <code>5 ≤ m,n ≤ 1000</code>
* <code>1 ≤ k ≤ 1000</code>
* <code>1 ≤ x[i]</code>, <code>xc ≤ m</code>, <code>1 ≤ y[i]</code>, <code>yc ≤ n</code>, pentru orice <code>1 ≤ i ≤ k</code>
* Eventualele intersecţii ale drumurilor cavalerilor nu influenţează rezultatele
* Pentru datele de test se garantează existenţa unei soluţii

= Exemplul 1: =
<code>camelotIN.txt</code>
 1
 8 8 2
 4 5
 1 2
 8 1
<code>camelotOUT.txt</code>
 2

= Exemplul 2: =
<code>camelotIN.txt</code>
 1
 1001 8 2
 4 5
 1 2
 8 1
<code>camelotOUT.txt</code>
 Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
from collections import deque

dx = [-2, -2, -1, -1, 1, 1, 2, 2]
dy = [1, -1, -2, 2, -2, 2, -1, 1]

def inmat(i, j, n, m):
    return 1 <= i <= n and 1 <= j <= m

def check_restrictions(n, m, k, c1, c2, positions):
    if not (5 <= n <= 1000 and 5 <= m <= 1000):
        return "Datele nu corespund restrictiilor impuse"
    if not (1 <= k <= 1000):
        return "Datele nu corespund restrictiilor impuse"
    if not (1 <= c1 <= m and 1 <= c2 <= n):
        return "Datele nu corespund restrictiilor impuse"
    for x, y in positions:
        if not (1 <= x <= m and 1 <= y <= n):
            return "Datele nu corespund restrictiilor impuse"
    return None

def lee(ir, jr, n, m, b, q):
    b[ir][jr] = 1
    q.append((ir, jr))
    
    while q:
        x, y = q.popleft()
        for d in range(8):
            ii, jj = x + dx[d], y + dy[d]
            if inmat(ii, jj, n, m) and b[ii][jj] == 0:
                b[ii][jj] = b[x][y] + 1
                q.append((ii, jj))

if __name__ == "__main__":
    with open("camelotIN.txt", "r") as fin, open("camelotOUT.txt", "w") as fout:
        op = int(fin.readline().strip())
        n, m, k = map(int, fin.readline().strip().split())
        c1, c2 = map(int, fin.readline().strip().split())
        
        positions = [tuple(map(int, fin.readline().strip().split())) for _ in range(k)]
        
        restriction_error = check_restrictions(n, m, k, c1, c2, positions)
        if restriction_error:
            fout.write(restriction_error)
        else:
            a = [[0] * 1001 for _ in range(1001)]
            b = [[0] * 1001 for _ in range(1001)]
            q = deque()
            
            lee(c1, c2, n, m, b, q)
            
            mini = float('inf')
            maxi = 0
            
            for x, y in positions:
                if b[x][y] < mini:
                    mini = b[x][y]
                if b[x][y] > maxi:
                    maxi = b[x][y]
            
            if op == 1:
                fout.write(str(mini - 1))
            else:
                fout.write(str(maxi - 1))

</syntaxhighlight>