1819 - Copaci

Enunț

Pe un teren dreptunghiular de dimensiuni m şi n, din loc în loc sunt plantaţi copaci. Pentru fiecare copac se cunosc rândul şi coloana pe care este plantat, între ei fiind spaţii neplantate. Doi copaci se consideră consecutivi dacă mergând pe coloane, numai de la nord către sud, între ei sunt doar spaţii neplantate.

Cerința

Să se determine cea mai mare distanţă dintre doi copaci consecutivi şi toate perechile de copaci între care există această distanţă.

Date de intrare

Fişierul copaciin.txt conţine pe prima linie, m, n si k (m numărul de randuri, n numărul de coloane şi k numărul de copaci), separate prin cate un spaţiu; pe fiecare dintre următoarele k linii, câte o pereche de numere x, y (separate prin cate un spaţiu) reprezentând rândul, respectiv coloana pe care se află un copac.

Date de ieșire

Fişierul copaciout.txt va conţine pe prima linie distanţa maximă dintre doi copaci consecutivi, iar pe fiecare dintre următoarele linii câte patru numere întregi x1, y1, x2, y2 (separate prin cate un spaţiu), reprezentând coordonatele (rândul şi coloana) a doi copaci consecutivi între care distanţa este maximă.

Observaţii

Distanţa dintre dintre doi copaci consecutivi este dată de numărul de spaţii neplantate dintre ei.

Dacă sunt mai multe perechi de copaci între care distanţa este maximă acestea se vor afişa în ordinea crescătoare a numărului de coloană.

Restricții și precizări

• 1 < m,n ≤ 500
• 2 ≤ k ≤ 10000

Exemplul 1

copaciin.txt

3 4 2

2 4

3 4

copaciout.txt

0

2 4 3 4

Explicație

Sunt 2 copaci plantaţi pe coloana a 4-a şi între ei nu se află nici un spaţiu neplantat.

Exemplul 2

copaciin.txt

6 7 7

1 1

1 4

2 6

3 3

4 2

5 4

6 3

copaciout.txt

8

1 1 4 2

5 4 2 6

Explicație

Sunt 7 copaci. Distanţa maximă între 2 copaci consecutivi este egală cu 8.

Sunt 2 perechi de copaci care se află la această distanţă. Prima pereche are copacii pe coloanele 1 respectiv 2, a doua pereche are copacii pe coloanele 4 respectiv 6.

Rezolvare

def is_valid(m, n, k):
    return 1 < m <= 500 and 1 < n <= 500 and 2 <= k <= 10000

with open("copaciin.txt", "r") as f_in:
    n, m, p = map(int, f_in.readline().split())
    a = [[0] * 501 for _ in range(501)]

    for _ in range(p):
        x, y = map(int, f_in.readline().split())
        a[x][y] = 1

l, lmax, st = 0, -1, -1

for j in range(1, m + 1):
    for i in range(1, n + 1):
        if a[i][j] == 1:
            if l > lmax and st != -1:
                lmax = l
            st = a[i][j]
            l = 0
        if a[i][j] == 0:
            l += 1

st = -1
with open("copaciout.txt", "w") as f_out:
    f_out.write(str(lmax) + "\n")
    dr = 0
    for j in range(1, m + 1):
        for i in range(1, n + 1):
            if a[i][j] == 1:
                if l == lmax and st != -1:
                    f_out.write(f"{dr} {st} {i} {j}\n")
                st, dr, l = j, i, 0
            if a[i][j] == 0:
                l += 1