4050 - amongus

Enunt

În jocul Among Us un echipaj încearcă să piloteze o navetă spațială. O parte din ei încearcă să saboteze misiunea. Acești „impostori” sunt de obicei periculoși și astfel astronauții (sau „crewmates”) trebuie să se ferească pe cât posibil de aceștia. Astronauții au studiat planul interiorului navetei și au constatat că este compartimentat în nxm cabine, dispuse pe n rânduri, câte m pe fiecare rând, iar din fiecare cabină se poate trece în oricare altă cabină alăturată situată într-una din cele 8 direcții (N, E, S, V, N-V, N-E, S-V, S-E). Astronautii au creat o matrice a codurilor asociind fiecărei cabine un număr din mulțimea {0,1,2} cu semnificația:

• cod 0 dacă este o cabină sigură (adică în cabină nu se află niciun impostor)
• cod 1 dacă în ea se află un impostor
• cod 2 dacă este un portal („vent”).

Cerinta

Cunoscând matricea codurilor, pentru a ajuta astronauții, vi se cere:

• 1) să determinați numărul total de cabine sigure, nu sunt neapărat accesibile, ce nu conțin portale
• 2) să marcați în matricea codurilor cu codul 3 fiecare cabină sigură (și accesibilă)
• 3) să determinați numărul portalelor situate în cabine accesibile.

Date de intrare

Fișierul de intrare amongusin.txt conține:

• pe prima linie numărul p reprezentând cerința care se rezolvă (1, 2 sau 3)
• pe a doua linie, două numere naturale n și m cu semnificația din enunț
• pe fiecare din următoarele n linii, câte m numere naturale din mulțimea {0,1,2}, separate prin câte un spațiu, reprezentând matricea de codificare a interiorului navetei spațiale.

Date de iesire

Fișierul de ieșire amongusout.txt va conține:

• dacă p=1, pe prima linie, un număr natural reprezentând răspunsul la cerința 1
• dacă p=2, n linii cu câte m numere naturale, separate prin câte un spațiu,reprezentând matricea codurilor modificată conform cerinței 2
• dacă p=3, pe prima linie, un număr natural reprezentând răspunsul la cerința 3.

Restrictii si precizari

• 1 ⩽ n, m ⩽ 100
• astronauții pot intra în naveta doar prin cabina de coordonate (1,1) ceea ce înseamnă că accesul în unele cabine nu se poate realiza deși sunt sigure
• în cazul în care în prima cabină se află un impostor, pentru oricare dintre cerințe, se va scrie în fișier mesajul misiune esuata
• pentru cerința 1, se va modifica în 3 codul fiecărei cabine sigure
• un portal poate fi situat doar într-o cabină sigură
• există și cabine sigure care nu conțin portale
• impostorii nu se deplasează în afara cabinei în care se află inițial

Exemplul 1

amongusin.txt

1

3 4

0 2 1 0

2 0 1 0

0 0 1 2

amongusout.txt

Datele introduse corespund restrictiilor impuse

6

Exemplul 2

amongusin.txt

8

-1 7

0 0 2 5

-8 6 1 0

0 0 0 -3

Datele introduse nu corespund restrictiilor impuse

Rezolvare

def numar_cabine_sigure(matrice, n, m):
    numar_sigure = 0
    for i in range(n):
        for j in range(m):
            if matrice[i][j] == 0:
                numar_sigure += 1
    return numar_sigure

def marcaza_cabine_sigure(matrice, n, m):
    for i in range(n):
        for j in range(m):
            if matrice[i][j] == 0:
                matrice[i][j] = 3

def numar_portale_accesibile(matrice, n, m):
    numar_portale = 0
    for i in range(n):
        for j in range(m):
            if matrice[i][j] == 2 and not are_impstor_in_jur(matrice, n, m, i, j):
                numar_portale += 1
    return numar_portale

def are_impstor_in_jur(matrice, n, m, i, j):
    for x in range(max(0, i-1), min(n, i+2)):
        for y in range(max(0, j-1), min(m, j+2)):
            if matrice[x][y] == 1:
                return True
    return False

def verificare(rezultat, p, n, m, matrice_initiala):
    if p == 1:
        return isinstance(rezultat, int) and 0 <= rezultat <= n * m
    elif p == 2:
        if not all(isinstance(row, list) and len(row) == m for row in rezultat):
            return False
        if not all(isinstance(elem, int) and 0 <= elem <= 3 for row in rezultat for elem in row):
            return False
        for i in range(n):
            for j in range(m):
                if matrice_initiala[i][j] == 0 and rezultat[i][j] != 3:
                    return False
        return True
    elif p == 3:
        return isinstance(rezultat, int) and 0 <= rezultat <= n * m

# Citire date de intrare
with open("amongusin.txt", "r") as file:
    p = int(file.readline().strip())
    n, m = map(int, file.readline().split())
    matrice_initiala = [list(map(int, file.readline().split())) for _ in range(n)]

# Rezolvare cerinte
if p == 1:
    rezultat = numar_cabine_sigure(matrice_initiala, n, m)
elif p == 2:
    rezultat = matrice_initiala.copy()
    marcaza_cabine_sigure(rezultat, n, m)
elif p == 3:
    rezultat = numar_portale_accesibile(matrice_initiala, n, m)

# Scriere rezultat în fișierul de ieșire
with open("amongusout.txt", "w") as file:
    if p == 1 or p == 3:
        file.write(str(rezultat) + "\n")
    elif p == 2:
        for linie in rezultat:
            file.write(" ".join(map(str, linie)) + "\n")

# Verificare rezultat
rezultat_corect = verificare(rezultat, p, n, m, matrice_initiala)
print("Rezultat corect:", rezultat_corect)

Explicatie

Se rezolva cerința 1. Matricea codurilor conține 6 camere sigure, codificate cu 0.