1142 - Lasere

Enunț

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.

Cerinţe

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.

Date de intrare

Fișierul de intrare laserein.txt 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.

Date de ieșire

Fișierul de ieșire lasereout.txt 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).

Restricții și precizări

• 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.

Exemplul 1

laserein.txt

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

lasereout.txt

6

Exemplul 2

laserein.txt

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

lasereout.txt

1

Rezolvare

def is_valid(x, y, direction, n):
    return 1 <= x <= n and 1 <= y <= n and 1 <= direction <= 4

def validare_matrice_element(element):
    return 0 <= element <= 9999

def valid_input(n, m):
    return 4 <= n <= 200 and 1 <= m <= 200

N = 204
INF = 10000
M = 10000

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

with open("laserein.txt", "r") as infile, open("lasereout.txt", "w") as outfile:
    cer = int(infile.readline().strip())
    n, m = map(int, infile.readline().split())

    A = [[0] * (N + 2) for _ in range(N + 2)]
    for i in range(1, n + 1):
        A[i][1:n + 1] = map(int, infile.readline().split())
    for i in range(n + 2):
        A[0][i] = A[i][0] = A[i][n + 1] = A[n + 1][i] = INF

    X = []
    nr = 0
    tr = 0
    B = [0] * (N + 1)
    for _ in range(m):
        x, y, direction = map(int, infile.readline().split())
        X.append({'x': x, 'y': y, 'dir': direction})

        if direction == 1:
            for i in range(x - 1, 0, -1):
                A[i][y] -= 1
        elif direction == 2:
            for i in range(y + 1, n + 1):
                A[x][i] -= 1
        elif direction == 3:
            for i in range(x + 1, n + 1):
                A[i][y] -= 1
        elif direction == 4:
            for i in range(y - 1, 0, -1):
                A[x][i] -= 1

    for i in range(1, n + 1):
        for j in range(1, n + 1):
            ok = all(A[i][j] <= A[i + dx[l]][j + dy[l]] for l in range(8))
            if ok:
                B[j] = 1
                nr += 1

        p1 = 0
        s = 1
        while s < n:
            if B[s] == 1:
                p1 = s
                while B[s]:
                    s += 1
                if s - p1 >= 2:
                    tr += 1
            else:
                s += 1

        B = [0] * (N + 1)

    if cer == 1:
        outfile.write(str(nr) + "\n")
    else:
        outfile.write(str(tr) + "\n")

if __name__=="-__main__":
    is_valid()
    validare_matrice_element()
    valid_input()