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.
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 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.
Date de ieșire
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).
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
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
Exemplul 2
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
Rezolvare
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
# 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)]
# Calculare rezultat
rezultat = rezolva_cerinta(c, n, m, teren, lasere)
# Scriere date de iesire
with open('lasereout.txt', 'w') as f:
f.write(str(rezultat) + '\n')