0884 - Paznici

Cerința

Se consideră o clădire de formă dreptunghiulară, formată din n*m camere dispuse sub forma unei matrice cu n linii și m coloane. Anumite camere sunt ocupate şi nu pot fi vizitate, celelalte sunt libere și pot fi vizitate. Dintr-o cameră se poate trece în altă cameră dacă ambele sunt libere și se învecinează pe linie sau pe coloană.

În anumite camere sunt paznici. Din motive de securitate, paznicii se pot deplasa din camera inițială în anumite camere libere din apropiere, dar fără a se îndepărta la o distanță mai mare decât o valoare cunoscută. Fiecare paznic va verifica periodic camerele libere în care poate ajunge.

Să se determine numărul de camere din clădire care nu sunt verificate de niciun paznic.

Date de intrare

Fișierul de intrare paznici.in conține pe prima linie trei numere n m p, reprezentând dimensiunile clădirii şi numărul de paznici.

Urmează n linii cu câte m caractere, care pot fi: -, reprezentând o cameră liberă, respectiv #, reprezentând o cameră ocupată.

Urmează p linii cu câte 3 valori i j d, reprezentând informaţiile despre paznici. i j reprezintă indicii camerei, iar d reprezintă distanţa pe care se poate deplasa acel paznic.

Date de ieșire

Fișierul de ieșire paznici.out va conține pe prima linie numărul C de camere care nu sunt vizitate de niciun paznic.

Restricții și precizări

• 1 ≤ n, m, p ≤ 200
• 1 ≤ i ≤ n
• 1 ≤ j ≤ m
• 0 ≤ d ≤ 40

Exemplu 1

Intrare

4 6 3
--#-#-
--##--

---

---

#

1 1 1
1 6 2
4 1 3

Iesire

4

Exemplu 2

Intrare

4
ENQUEUE George
DEQUEUE
DEQUEUE
ENQUEUE Paul

Iesire

Eroare: coada goală ['Paul']

Datele de intrare nu corespund restricțiilor impuse.

Rezolvare

<syntaxhighlight lang="python" line> def in_bounds(x, y, n, m):

   return 0 <= x < n and 0 <= y < m

def mark_guard_reachable(grid, visited, x, y, d, n, m):

   directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]  # N, S, W, E
   queue = [(x, y, 0)]
   visited[x][y] = True

   while queue:
       cx, cy, dist = queue.pop(0)
       if dist < d:
           for dx, dy in directions:
               nx, ny = cx + dx, cy + dy
               if in_bounds(nx, ny, n, m) and not visited[nx][ny] and grid[nx][ny] == '-':
                   visited[nx][ny] = True
                   queue.append((nx, ny, dist + 1))

def main():

   with open("paznici.in", "r") as f:
       n, m, p = map(int, f.readline().strip().split())
       grid = [list(f.readline().strip()) for _ in range(n)]
       guards = [tuple(map(int, f.readline().strip().split())) for _ in range(p)]

   visited = [[False for _ in range(m)] for _ in range(n)]

   for guard in guards:
       i, j, d = guard
       mark_guard_reachable(grid, visited, i - 1, j - 1, d, n, m)

   unvisited_count = sum(1 for i in range(n) for j in range(m) if grid[i][j] == '-' and not visited[i][j])

   with open("paznici.out", "w") as f:
       f.write(f"{unvisited_count}\n")

if __name__ == "__main__":

   main()

if __name__ == "__main__":

   main()

</syntaxhighlight>