Vizualizare sursă pentru „2167 - alee”

== Enunt ==

Parcul oraşului a fost neglijat mult timp, astfel că acum toate aleile sunt distruse. Prin urmare, anul acesta Primăria şi-a propus să facă reamenajări. Parcul are forma unui pătrat cu latura de <code>n</code> metri și este înconjurat de un gard care are exact două porți. Proiectanții de la Primărie au realizat o hartă a parcului și au trasat pe hartă un caroiaj care împarte parcul în <code>nxn</code> zone pătrate cu latura de <code>1</code> metru. Astfel harta parcului are aspectul unei matrice pătratice cu <code>n</code> linii și <code>n</code> coloane. Liniile și respectiv coloanele sunt numerotate de la <code>1</code> la <code>n</code>. Elementele matricei corespund zonelor pătrate de latură <code>1</code> metru. O astfel de zonă poate să conțină un copac sau este liberă. Edilii orașului doresc să paveze cu un număr minim de dale pătrate cu latura de <code>1</code> metru zonele libere (fără copaci) ale parcului, astfel încât să se obțină o alee continuă de la o poartă la alta.

= Cerința =
Scrieți un program care să determine numărul minim de dale necesare pentru construirea unei alei continue de la o poartă la cealaltă.

= Date de intrare =
Fișierul de intrare <code>aleeIN.txt</code> conține pe prima linie două valori naturale <code>n</code> și <code>m</code> separate printr-un spațiu, reprezentând dimensiunea parcului, respectiv numărul de copaci care se găsesc în parc. Fiecare dintre următoarele <code>m</code> linii conține câte două numere naturale <code>x</code> și <code>y</code> separate printr-un spațiu, reprezentând pozițiile copacilor în parc (<code>x</code> reprezintă linia, iar <code>y</code> reprezintă coloana zonei în care se află copacul). Ultima linie a fișierului conține patru numere naturale <code>x1 y1 x2 y2</code>, separate prin câte un spațiu, reprezentând pozițiile celor două porți (<code>x1</code>, <code>y1</code> reprezintă linia și respectiv coloana zonei ce conține prima poartă, iar <code>x2</code>, <code>y2</code> reprezintă linia și respectiv coloana zonei ce conține cea de a doua poartă).

= Date de ieșire =
Fișierul de ieșire <code>aleeOUT.txt</code> va conţine o singură linie pe care va fi scris un număr natural care reprezintă numărul minim de dale necesare pentru construirea aleii. Î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>1 ≤ n ≤ 175</code>
* <code>1 ≤ m < n*n</code>
* Aleea este continuă dacă oricare două plăci consecutive au o latură comună.
* Aleea începe cu zona unde se găsește prima poartă și se termină cu zona unde se găsește cea de a doua poartă.
* Pozițiile porților sunt distincte şi corespund unor zone libere.
* Pentru datele de test există întotdeauna soluție.

= Exemplul 1: =
<code>aleeIN.txt</code>
 8 6 
 2 7
 3 3
 4 6
 5 4
 7 3
 7 5 
 1 1 8 8
<code>aleeOUT.txt</code>
 15

=== Explicație ===
O modalitate de a construi aleea cu număr minim de dale este:

<code>OOO-----</code>

<code>--OO--x-</code>

<code>--xO----</code>

<code>---OOx--</code>

<code>---xO---</code>

<code>----OO--</code>

<code>--x-xOO-</code>

<code>------OO</code>

(cu <code>X</code> am marcat copacii, cu <code>-</code> zonele libere, iar cu <code>O</code> dalele aleii).

== Exemplul 2: ==
<code>aleeIN.txt</code>
 200 6 
 2 7
 3 3
 4 6
 5 4
 7 3
 7 5 
 1 1 8 8
<code>aleeOUT.txt</code>
 Datele nu corespund restrictiilor impuse

== Rezolvare ==

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

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

def read():
    global n, m, x1, y1, x2, y2, a
    with open("aleeIN.txt", "r") as f:
        n, m = map(int, f.readline().split())
        if not check_restrictions():
            return False
        a = [[0] * (n + 1) for _ in range(n + 1)]
        for _ in range(m):
            i, j = map(int, f.readline().split())
            a[i][j] = -1
        x1, y1, x2, y2 = map(int, f.readline().split())
    return True

def check_restrictions():
    if not (1 <= n <= 175):
        with open("aleeOUT.txt", "w") as f:
            f.write("Datele nu corespund restrictiilor impuse\n")
        return False
    if not (1 <= m < n * n):
        with open("aleeOUT.txt", "w") as f:
            f.write("Datele nu corespund restrictiilor impuse\n")
        return False
    return True

def OK(i, j):
    if i < 1 or i > n or j < 1 or j > n:
        return False
    if a[i][j] == -1:
        return False
    return True

def lee():
    global a
    Q = deque([(x1, y1)])
    a[x1][y1] = 1
    while Q:
        i, j = Q.popleft()
        for k in range(4):
            ni = i + dx[k]
            nj = j + dy[k]
            if OK(ni, nj) and a[ni][nj] < 1:
                a[ni][nj] = a[i][j] + 1
                Q.append((ni, nj))

def main():
    if not read():
        return
    lee()
    with open("aleeOUT.txt", "w") as f:
        f.write(str(a[x2][y2]) + "\n")

if __name__ == "__main__":
    main()

</syntaxhighlight>