Editing 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 <code>M</code> linii şi <code>N</code> coloane. Cele <code>M x N</code> celule ale castelului sunt numerotate de la <code>1</code> la <code>M x N</code> î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 <code>i</code> conţine cheia cu numărul <code>i</code>. 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.

= Cerința =
Deşi eşti convins că prinţesa nu va scăpa din castel, eşti curios să afli câte dintre cele <code>M x N</code> 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 <code>castelIN.txt</code> conţine pe prima linie trei numere naturale <code>M N K</code> 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 <code>M</code> linii se află câte <code>N</code> numere naturale cuprinse între <code>1</code> şi <code>M x N</code> reprezentând cheile necesare deschiderii fiecăreia dintre camere.

= Date de ieșire =
Fișierul de ieșire <code>castelOUT.txt</code> 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 =

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

= Exemplul 1: =
<code>castelIN.txt</code>
 4 3 1
 1 1 4
 1 6 2
 6 9 8
 12 10 11
<code>castelOUT.txt</code>
 7

= Exemplul 1: =
<code>castelIN.txt</code>
 151 3 1
 1 1 4
 1 6 2
 6 9 8
 12 10 11
<code>castelOUT.txt</code>
 Datele nu corespund restrictiilor impuse

=== Explicație ===
Prinţesa porneşte din camera <code>1</code>. Aici foloseşe cheia <code>1</code> şi intră în camera <code>4</code>. Se întoarce în camera <code>1</code> şi descuie camera <code>2</code>. Foloseşte cheia luată din camera <code>4</code> şi descuie camera <code>3</code>. În acest moment ea deţine cheile <code>1</code>, <code>2</code>, <code>3</code> şi <code>4</code>. Foloseşte cheia <code>2</code> şi intră în camera <code>6</code>, apoi foloseşte cheia <code>6</code> şi intră în camera <code>5</code>, apoi în camera <code>4</code>, de unde, folosind cheia luată din camera <code>6</code> intră în camera <code>7</code>. La final prinţesa are cheile <code>1</code>, <code>2</code>, <code>3</code>, <code>4</code>, <code>5</code>, <code>6</code>, <code>7</code> şi nu mai poate deschide nici o altă cameră.
:

== Rezolvare ==

<syntaxhighlight lang="python3" line="1">
from collections import deque

def verifica_restrictii(n, m, cam):
    if not (1 <= n <= 150 and 1 <= m <= 150 and 1 <= cam <= n * m):
        with open("castelOUT.txt", "w") as fout:
            fout.write("Datele nu corespund restrictiilor impuse\n")
        return False
    return True

def main():
    di = [0, 0, 1, -1]
    dj = [1, -1, 0, 0]
    N = 155

    with open("castelIN.txt", "r") as fin:
        n, m, cam = map(int, fin.readline().split())
        if not verifica_restrictii(n, m, cam):
            return
        mat = [[0] * (m + 1) for _ in range(n + 1)]
        for i in range(1, n + 1):
            mat[i][1:m + 1] = map(int, fin.readline().split())

    sx = cam // m + 1
    sy = cam % m
    if cam % m == 0:
        sx -= 1
        sy = m

    q = deque([(sx, sy)])
    viz = [False] * (N * N)
    deja = [[False] * (m + 1) for _ in range(n + 1)]
    astept = [[] for _ in range(N * N)]

    while q:
        x, y = q.popleft()
        CAM = (x - 1) * m + y
        deja[x][y] = viz[CAM] = True

        for cam in astept[CAM]:
            ny = cam % m
            nx = cam // m + 1
            if cam % m == 0:
                nx -= 1
                ny = m
            if not deja[nx][ny]:
                q.append((nx, ny))
        
        astept[CAM].clear()

        for dir in range(4):
            nx = x + di[dir]
            ny = y + dj[dir]
            cam = (nx - 1) * m + ny
            if 1 <= nx <= n and 1 <= ny <= m:
                if viz[mat[nx][ny]]:
                    if not deja[nx][ny]:
                        q.append((nx, ny))
                else:
                    astept[mat[nx][ny]].append(cam)

    res = sum(deja[i][j] for i in range(1, n + 1) for j in range(1, m + 1))

    with open("castelOUT.txt", "w") as fout:
        fout.write(str(res) + "\n")

if __name__ == "__main__":
    main()

</syntaxhighlight>