Editing 3404 - castel3 (section)

= 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>