3404 - castel3

Enunt

Înspăimântătorii tăi luptători au răpit-o pe Prinţesa Ghiocela şi au închis-o în castelul tău de pe vârful Muntelui Pleşuv. Deoarece eşti un geniu malefic, te-ai hotărât să îi oferi prinţesei iluzia unei şanse de evadare. Castelul tău are forma unui caroiaj cu M linii şi N coloane. Cele M x N celule ale castelului sunt numerotate de la 1 la M x N în ordinea parcurgerii caroiajului pe linii de sus în jos, iar pe aceeaşi linie în ordinea coloanelor de la stânga la dreapta. În fiecare dintre celulele castelului ai pus câte o cheie, mai precis celula i conţine cheia cu numărul i. Evident, pentru a intra într-o cameră, prinţesa are nevoie de o anume cheie care permite deschiderea acesteia. Mai mult, dintr-o cameră prinţesa se poate deplasa într-un moment numai într-una dintre cele maximum patru camere adiacente pe orizontală şi verticală, doar dacă deţine cheia necesară deschiderii sale. Odată ce a intrat într-o cameră şi a obţinut o cheie, prinţesa o păstrează şi poate să o utilizeze ori de câte ori doreşte.

Cerinta

Deşi eşti convins că prinţesa nu va scăpa din castel, eşti curios să afli câte dintre cele M x N camere îi sunt accesibile. Date fiind dimensiunile castelului, camera în care se află iniţial prinţesa şi cheile necesare deschiderii fiecăreia dintre camere, află răspunsul la această întrebare presantă.

Date de intrare

Fișierul de intrare castel.in conţine pe prima linie trei numere naturale M N K separate prin câte un spaţiu reprezentând dimensiunile castelului, respectiv numărul camerei în care se află iniţial prinţesa. Urmează descrierea castelului. Pe fiecare dintre următoarele M linii se află câte N numere naturale cuprinse între 1 şi M x N reprezentând cheile necesare deschiderii fiecăreia dintre camere.

Date de ieșire

Fișierul de ieșire castel.out va conţine o singură linie pe care va fi scris un singur număr natural reprezentând numărul de camere accesibile prinţesei.

Restricții și precizări

• 1 ≤ M, N ≤ 150
• 1 ≤ K ≤ M * N
• Odată ce prinţesa a păşit într-o cameră, respectiva cameră va rămâne pentru totdeauna deschisă.

Exemplul 1

castelin.txt

4 3 1

1 1 4

1 6 2

6 9 8

12 10 11

castelout.txt

Datele introduse corespund restrictiilor impuse.

7

Exemplul 2

castelin.txt

0 8 9

-2 -3 -4

123 433 4322

9383 -12 -2

-098 -9087 0

castelout.txt

Datele de intrare nu corespund restrictiilor impuse.

Rezolvare

<syntaxhighlight lang="python3" line="1">

def numar_camere_accesibile(M, N, camera_initiala, chei_necesare):

   # Pasul 1: Construirea grafului
   graf = construieste_graf(M, N, chei_necesare)

   # Pasul 2: Căutarea în graf
   chei_prințesa = set()
   camere_accesibile = set()

   def dfs(camera):
       nonlocal chei_prințesa, camere_accesibile
       camere_accesibile.add(camera)

       for vecin in graf[camera]:
           cheie_necesara = graf[camera][vecin]
           if cheie_necesara in chei_prințesa:
               if vecin not in camere_accesibile:
                   dfs(vecin)

   dfs(camera_initiala)

   # Pasul 3: Numărăm camerele accesibile
   return len(camere_accesibile)

def construieste_graf(M, N, chei_necesare):

   graf = {}
   for i in range(1, M * N + 1):
       graf[i] = {}

   for i in range(1, M + 1):
       for j in range(1, N + 1):
           camera = (i - 1) * N + j

           # Verificăm camerele adiacente pe orizontală și verticală
           if i > 1:
               vecin = camera - N
               cheie = chei_necesare[vecin - 1]
               graf[camera][vecin] = cheie
               graf[vecin][camera] = cheie

           if i < M:
               vecin = camera + N
               cheie = chei_necesare[camera - 1]
               graf[camera][vecin] = cheie
               graf[vecin][camera] = cheie

           if j > 1:
               vecin = camera - 1
               cheie = chei_necesare[vecin - 1]
               graf[camera][vecin] = cheie
               graf[vecin][camera] = cheie

           if j < N:
               vecin = camera + 1
               cheie = chei_necesare[camera - 1]
               graf[camera][vecin] = cheie
               graf[vecin][camera] = cheie

   return graf

rezultat = numar_camere_accesibile(M, N, camera_initiala, chei_necesare) print(rezultat)

</syntaxhighlight>