Editing 1142 - Lasere

Se consideră un teren reprezentat printr-o matrice cu n linii şi n coloane având elemente numere naturale. În fiecare element al matricei este memorată înălţimea zonei de teren corespunzătoare ca poziţie elementului respectiv. Pe acest teren sunt amplasate m lasere, în poziţii cunoscute. Un laser este îndreptat spre unul dintre cele 4 puncte cardinale, codificate prin numere astfel: Nord prin valoarea 1, Est prin valoarea 2, Sud prin valoarea 3 şi respectiv Vest prin valoarea 4. Fiecare laser va executa o singură tragere şi ca urmare va scădea cu 1 valorile tuturor elementelor din matrice din direcţia sa de tragere, exceptând poziţia laserului respectiv.

După efectuarea tuturor tragerilor, se caută poziţiile tuturor gropilor şi ale tranşeelor.

Numim groapă un element din matrice pentru care toate cele 8 elemente învecinate pe linie, coloană sau diagonale au valori mai mari sau egale decât el.

Numim tranşee o secvenţă maximală formată din două sau mai multe gropi situate pe aceeaşi linie, pe coloane consecutive. Secvenţa se numeşte maximală dacă nu mai poate fi prelungită la niciunul dintre capete.

'''''<u><big>Cerinţe</big></u>'''''

Cunoscând configuraţia terenului şi amplasarea laserelor, să se rezolve una dintre următoarele două cerinţe:

1. să se determine numărul de gropi din teren, după executarea tragerilor;

2. să se determine numărul de tranşee existente, după executarea tragerilor.

<u>'''''Date de intrare'''''</u>

Fișierul de intrare lasere.in conține pe prima linie un număr natural c care reprezintă cerinţa ce urmează să fie rezolvată (1 sau 2). Pe a doua linie se află două numere naturale n şi m, reprezentând numărul de linii şi de coloane ale matricei, respectiv numărul de lasere. Pe următoarele n linii se află câte n numere naturale, reprezentând elementele matricei. Pe următoarele m linii sunt descrise cele m lasere, câte un laser pe o linie. Pe o linie care descrie un laser se află 3 numere naturale i j d, cu semnificaţia că se află un laser pe linia i şi coloana j (1≤i,j≤n), care trage în direcţia d (1≤d≤4). Valorile situate pe aceeaşi linie sunt separate prin spaţiu.

<u>'''''Date de ieșire'''''</u>

Fișierul de ieșire lasere.out va conține pe prima linie un singur număr natural. Acest număr reprezintă numărul de gropi (dacă c=1) sau numărul de tranşee (dacă c=2).

''<u>'''Restricții și precizări'''</u>''

4 ≤ n ≤ 200

1 ≤ m ≤ 200

Numerotarea liniilor şi a coloanelor este de la 1 la n.

Elementele matricei din fişierul de intrare sunt numere naturale de maxim 4 cifre.

Poziţiile laserelor sunt distincte.

Pentru teste valorând 30% din punctaj cerinţa este 1.

'''''<u>Exemplul 1</u>'''''

lasere.in

1

5 3

1 1 3 4 5

8 7 6 5 4

9 3 5 6 7

1 1 1 9 8

1 1 1 5 6

2 3 3

4 4 4

1 4 2

lasere.out

6

'''''<u>Exemplul 2</u>'''''

lasere.in

2

5 3

1 1 3 4 5

8 7 6 5 4

9 3 5 6 7

1 1 1 9 8

1 1 1 5 6

2 3 3

4 4 4

1 4 2

lasere.out

1

''<u>'''Rezolvare'''</u>''

def rezolva_cerinta(c, n, m, teren, lasere):

    def executa_trageri(laser, teren):

        i, j, d = laser

        i -= 1

        j -= 1

        if d == 1:  # Tragere la Nord

            for x in range(i - 1, -1, -1):

                if x >= 0:

                    teren[x][j] -= 1

        elif d == 2:  # Tragere la Est

            for y in range(j + 1, n):

                if y < n:

                    teren[i][y] -= 1

        elif d == 3:  # Tragere la Sud

            for x in range(i + 1, n):

                if x < n:

                    teren[x][j] -= 1

        elif d == 4:  # Tragere la Vest

            for y in range(j - 1, -1, -1):

                if y >= 0:

                    teren[i][y] -= 1

    def este_groapa(x, y, teren):

        for i in range(max(0, x - 1), min(n, x + 2)):

            for j in range(max(0, y - 1), min(n, y + 2)):

                if i < n and j < n and teren[i][j] < teren[x][y]:

                    return False

        return True

    def identifica_groape_si_transee(teren):

        gropi = 0

        transee = 0

        for i in range(n):

            for j in range(n):

                if este_groapa(i, j, teren):

                    gropi += 1

        for i in range(n):

            j = 0

            while j < n:

                if este_groapa(i, j, teren):

                    transee += 1

                    while j < n and este_groapa(i, j, teren):

                        j += 1

                else:

                    j += 1

        return gropi if c == 1 else transee

    for laser in lasere:

        executa_trageri(laser, teren)

    rezultat = identifica_groape_si_transee(teren)

    return rezultat

<nowiki>#</nowiki> Citire date de intrare

with open('laserein.txt', 'r') as f:

    c = int(f.readline().strip())

    n, m = map(int, f.readline().split())

    teren = [list(map(int, f.readline().split())) for _ in range(n)]

    lasere = [list(map(int, f.readline().split())) for _ in range(m)]

<nowiki>#</nowiki> Calculare rezultat

rezultat = rezolva_cerinta(c, n, m, teren, lasere)

<nowiki>#</nowiki> Scriere date de iesire

with open('lasereout.txt', 'w') as f:

    f.write(str(rezultat) + '\n')