View source for 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>