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.

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 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 castelIN.txt 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 castelOUT.txt 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

7

Exemplul 1:

castelIN.txt

151 3 1
1 1 4
1 6 2
6 9 8
12 10 11

castelOUT.txt

Datele nu corespund restrictiilor impuse

Explicație

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

Rezolvare

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()